마디 n개로 된 계산 나무가 있다. 마디에는 1번부터 n번까지 번호가 있고, 1번 마디가 뿌리다.
첫 줄에 n과 입력값의 수 m이, 다음 n줄에 1번부터 차례로 마디가 하나씩 주어진다. 마디는 다음 여섯 가지 가운데 하나다.
num v의 값은 정수 v다.
in k의 값은 질문의 k번째 입력값이다.
add a b의 값은 (a번 마디의 값) + (b번 마디의 값)이고, sub a b의 값은 (a번 마디의 값) − (b번 마디의 값)이다.
div a b의 값은 (a번 마디의 값) ÷ (b번 마디의 값)의 몫이다. 몫은 소수 부분을 0 쪽으로 버린다(−7 ÷ 2는 −3). b번 마디의 값이 0이면 이 마디는 계산할 수 없다.
if a b c d는 먼저 a번 마디와 b번 마디의 값을 구한다. (a번 마디의 값) < (b번 마디의 값)이면 c번 마디의 값이 이 마디의 값이고, 아니면 d번 마디의 값이 이 마디의 값이다. 고르지 않은 쪽 마디는 계산하지 않는다.
어떤 마디를 계산하는 데 필요한 마디 가운데 하나라도 계산할 수 없으면, 그 마디도 계산할 수 없다.
그다음 줄에 질문 수 q가, 다음 q줄에 질문마다 입력값 m개가 빈칸으로 나뉘어 주어진다.
마디 값을 돌려주는 재귀 함수를 만들어 풀어 보자. '계산할 수 없음'은 그 함수가 따로 표시한 값으로 돌려주거나, 언어에 맞게 예외로 알린다.
질문마다 뿌리의 값을 한 줄에 출력하라. 뿌리를 계산할 수 없으면 "오류"를 출력하라.
입력
1 ≤ n ≤ 999, 1 ≤ m ≤ 10, 1 ≤ q ≤ 300. 모든 마디의 a, b, c, d를 통틀어 2부터 n까지의 번호가 정확히 한 번씩 나오고 1은 나오지 않는다. 그 마디들을 자식이라 할 때, 자식의 번호는 부모의 번호보다 크다. 뿌리에서 잎까지의 마디 수는 500 이하다. 1 ≤ k ≤ m. v와 입력값은 -1,000,000 이상 1,000,000 이하의 정수다. 계산할 수 있는 마디라면 고르지 않은 쪽 마디까지 포함해 모든 마디의 값의 절댓값이 1,000,000,000 이하다
출력
q줄
예시 1 · stdin
9 1
if 2 3 4 7
in 1
num 0
div 5 6
num 100
in 1
sub 8 9
num 0
in 1
4
5
-7
0
-3
stdout
-5
-14
0
-33
예시 2 · stdin
7 3
add 2 3
in 1
div 4 5
num -7
sub 6 7
in 2
in 3
4
1 3 1
0 5 5
-1 9 2
4 2 4
stdout
-2
오류
-2
7
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
'값이 없음'을 돌려주는 방법이 언어마다 달라요. Python None, JS·TS null(TS는 number | null로 적고 === null을 물어야 number로 좁혀져요), C# int?, C++ std::optional<int>, 크레이콘 빈값이에요. C는 성공 여부를 돌려주고 값은 포인터 int *out에 넣어요. Java는 예외로 풀었어요: int를 0으로 나누면 /가 ArithmeticException을 던지고, 예외는 부른 함수들을 거쳐 맨 위의 catch까지 저절로 올라가요. 함정 ① 따로 표시할 값을 고르기: -1이나 0을 '계산할 수 없음'으로 쓰면 올바른 답 -1·0과 섞여요. ② 고르지 않은 쪽도 계산하기: c = value(...), d = value(...)를 먼저 구해 두고 고르면, 고르지 않은 쪽의 0 나누기 때문에 "error"가 나와요. ③ 재귀에서 return을 빠뜨리기: Python은 None, JS는 undefined가 조용히 돌아가요. C는 값이 정해지지 않고, Java·C#은 컴파일 오류예요. ④ 0으로 나누기: Python ZeroDivisionError, Java ArithmeticException, C# DivideByZeroException, 크레이콘 수학.몫은 멈추고, C·C++은 정의되지 않은 동작이에요. JS·TS는 멈추지 않고 Infinity·NaN을 줘요. ⑤ 몫: Python //는 아래로 내려서 -7 // 2가 -4예요. 크레이콘 /는 소수까지 나누니 수학.몫을 써요. ⑥ C#의 int?는 + - /에서 null을 알아서 넘기지만 a < b는 한쪽이 null이면 그냥 false라서, 확인하지 않으면 오류 대신 d 쪽 값이 나와요. 크레이콘은 빈값으로 계산하거나 크기를 견주면 멈춰요.
Pythonmain.py · 43 줄
import sysdata = sys.stdin.read().split("\n")n, m = map(int, data[0].split())nodes = [None] + [data[i].split() for i in range(1, n + 1)]q = int(data[n + 1])def div(a, b): # 0 쪽으로 버리는 몫. Python의 //는 아래로 내려서 음수에서 다르다 qt = abs(a) // abs(b) return qt if (a < 0) == (b < 0) else -qtdef value(i, x): """i번 마디의 값을 돌려준다. 계산할 수 없으면 None을 돌려준다.""" op, *args = nodes[i] if op == "num": return int(args[0]) if op == "in": return x[int(args[0]) - 1] a = value(int(args[0]), x) if a is None: return None # 실패는 곧바로 위로 돌려보낸다 b = value(int(args[1]), x) if b is None: return None if op == "add": return a + b if op == "sub": return a - b if op == "div": return None if b == 0 else div(a, b) # if: 고른 쪽 하나만 계산한다 return value(int(args[2]) if a < b else int(args[3]), x)out = []for line in data[n + 2:n + 2 + q]: x = list(map(int, line.split())) v = value(1, x) out.append("오류" if v is None else str(v)) # 0이나 -1도 올바른 값이라 None으로 가른다print("\n".join(out))
JavaScriptmain.js · 28 줄
const data = require("fs").readFileSync(0, "utf8").split("\n");const [n] = data[0].split(" ").map(Number);const nodes = [null];for (let i = 1; i <= n; i++) nodes.push(data[i].trim().split(" "));const q = Number(data[n + 1]);// i번 마디의 값을 돌려준다. 계산할 수 없으면 null을 돌려준다function value(i, x) { const [op, ...args] = nodes[i]; const k = args.map(Number); if (op === "num") return k[0]; if (op === "in") return x[k[0] - 1]; const a = value(k[0], x); if (a === null) return null; // 실패는 곧바로 위로 돌려보낸다 const b = value(k[1], x); if (b === null) return null; if (op === "add") return a + b; if (op === "sub") return a - b; if (op === "div") return b === 0 ? null : Math.trunc(a / b); // JS는 0으로 나눠도 멈추지 않고 Infinity를 준다 return value(a < b ? k[2] : k[3], x); // if: 고른 쪽 하나만 계산한다}const out = [];for (const line of data.slice(n + 2, n + 2 + q)) { const v = value(1, line.trim().split(" ").map(Number)); out.push(v === null ? "오류" : String(v)); // 0도 올바른 값이라 !v로 묻지 않는다}console.log(out.join("\n"));
TypeScriptmain.ts · 30 줄
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").split("\n");const [n] = data[0].split(" ").map(Number);const nodes: string[][] = [[]];for (let i = 1; i <= n; i++) nodes.push(data[i].trim().split(" "));const q = Number(data[n + 1]);// i번 마디의 값을 돌려준다. 계산할 수 없으면 null을 돌려준다function value(i: number, x: number[]): number | null { const [op, ...args] = nodes[i]; const k = args.map(Number); if (op === "num") return k[0]; if (op === "in") return x[k[0] - 1]; const a = value(k[0], x); if (a === null) return null; // 실패는 곧바로 위로 돌려보낸다(검사해야 a가 number로 좁혀진다) const b = value(k[1], x); if (b === null) return null; if (op === "add") return a + b; if (op === "sub") return a - b; if (op === "div") return b === 0 ? null : Math.trunc(a / b); // JS는 0으로 나눠도 멈추지 않고 Infinity를 준다 return value(a < b ? k[2] : k[3], x); // if: 고른 쪽 하나만 계산한다}const out: string[] = [];for (const line of data.slice(n + 2, n + 2 + q)) { const v = value(1, line.trim().split(" ").map(Number)); out.push(v === null ? "오류" : String(v)); // 0도 올바른 값이라 !v로 묻지 않는다}console.log(out.join("\n"));
JavaMain.java · 50 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static String[] op; static int[][] arg; // i번 마디의 값을 돌려준다. 0으로 나누면 Java의 / 가 ArithmeticException을 던지고, // 그 예외가 부른 쪽들을 거쳐 맨 위까지 올라간다 static int value(int i, int[] x) { int[] k = arg[i]; switch (op[i]) { case "num": return k[0]; case "in": return x[k[0] - 1]; case "add": return value(k[0], x) + value(k[1], x); case "sub": return value(k[0], x) - value(k[1], x); case "div": return value(k[0], x) / value(k[1], x); // int의 / 는 0 쪽으로 버린다 default: // if: 고른 쪽 하나만 계산한다 return value(k[0], x) < value(k[1], x) ? value(k[2], x) : value(k[3], x); } } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int n = Integer.parseInt(first[0]); op = new String[n + 1]; arg = new int[n + 1][]; for (int i = 1; i <= n; i++) { String[] p = in.readLine().trim().split(" "); op[i] = p[0]; arg[i] = new int[p.length - 1]; for (int j = 1; j < p.length; j++) arg[i][j - 1] = Integer.parseInt(p[j]); } int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int t = 0; t < q; t++) { String[] p = in.readLine().trim().split(" "); int[] x = new int[p.length]; for (int j = 0; j < p.length; j++) x[j] = Integer.parseInt(p[j]); try { out.append(value(1, x)).append('\n'); } catch (ArithmeticException e) { out.append("오류\n"); } } System.out.print(out); }}
C#Main.cs · 50 줄
using System;using System.Linq;using System.Text;class Program{ static string[] op = Array.Empty<string>(); static int[][] arg = Array.Empty<int[]>(); // i번 마디의 값을 돌려준다. 계산할 수 없으면 null(int?)을 돌려준다 static int? Value(int i, int[] x) { int[] k = arg[i]; if (op[i] == "num") return k[0]; if (op[i] == "in") return x[k[0] - 1]; int? a = Value(k[0], x); if (a is null) return null; // 실패는 곧바로 위로 돌려보낸다 int? b = Value(k[1], x); if (b is null) return null; switch (op[i]) { case "add": return a + b; case "sub": return a - b; case "div": return b == 0 ? null : a / b; // int의 / 는 0 쪽으로 버린다 default: return Value(a < b ? k[2] : k[3], x); // if: 고른 쪽 하나만 계산한다 } } static void Main() { int n = int.Parse(Console.ReadLine().Split(' ')[0]); op = new string[n + 1]; arg = new int[n + 1][]; for (int i = 1; i <= n; i++) { string[] p = Console.ReadLine().Trim().Split(' '); op[i] = p[0]; arg[i] = p.Skip(1).Select(int.Parse).ToArray(); } int q = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int t = 0; t < q; t++) { int[] x = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray(); int? v = Value(1, x); sb.Append(v is null ? "오류" : v.ToString()).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 55 줄
#include <iostream>#include <optional>#include <string>#include <vector>struct Node { std::string op; std::vector<int> k;};std::vector<Node> nodes;std::vector<int> x;// i번 마디의 값을 돌려준다. 계산할 수 없으면 값이 없는 optional(std::nullopt)std::optional<int> value(int i) { const Node &nd = nodes[i]; if (nd.op == "num") return nd.k[0]; if (nd.op == "in") return x[nd.k[0] - 1]; auto a = value(nd.k[0]); if (!a) return std::nullopt; // 실패는 곧바로 위로 돌려보낸다 auto b = value(nd.k[1]); if (!b) return std::nullopt; if (nd.op == "add") return *a + *b; if (nd.op == "sub") return *a - *b; if (nd.op == "div") { if (*b == 0) return std::nullopt; return *a / *b; // 0 쪽으로 버린다 } return value(*a < *b ? nd.k[2] : nd.k[3]); // if: 고른 쪽 하나만 계산한다}int main() { std::ios::sync_with_stdio(false); int n, m, q; std::cin >> n >> m; nodes.resize(n + 1); for (int i = 1; i <= n; i++) { Node &nd = nodes[i]; std::cin >> nd.op; int cnt = nd.op == "if" ? 4 : (nd.op == "num" || nd.op == "in") ? 1 : 2; nd.k.resize(cnt); for (int &v : nd.k) std::cin >> v; } std::cin >> q; x.resize(m); std::string out; for (int t = 0; t < q; t++) { for (int &v : x) std::cin >> v; auto v = value(1); out += v ? std::to_string(*v) : "오류"; out += '\n'; } std::cout << out; return 0;}
Cmain.c · 45 줄
#include <stdio.h>#include <string.h>static char op[1001]; /* n a s d i: num add sub div if, 'x'는 in */static int arg[1001][4];static int x[10];/* i번 마디의 값을 *out에 넣고 1을 돌려준다. 계산할 수 없으면 0을 돌려준다. 값과 성공 여부를 따로 돌려주니 -1이나 0도 올바른 값으로 쓸 수 있다 */static int value(int i, int *out) { int *k = arg[i], a, b; if (op[i] == 'n') { *out = k[0]; return 1; } if (op[i] == 'x') { *out = x[k[0] - 1]; return 1; } if (!value(k[0], &a) || !value(k[1], &b)) return 0; /* 실패는 곧바로 위로 */ switch (op[i]) { case 'a': *out = a + b; return 1; case 's': *out = a - b; return 1; case 'd': if (b == 0) return 0; /* C에서 0으로 나누면 정의되지 않은 동작 */ *out = a / b; /* C99부터 0 쪽으로 버린다 */ return 1; default: /* if: 고른 쪽 하나만 계산한다 */ return value(a < b ? k[2] : k[3], out); }}int main(void) { int n, m, q; char name[8]; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%7s", name); int cnt = strcmp(name, "if") == 0 ? 4 : strcmp(name, "num") == 0 || strcmp(name, "in") == 0 ? 1 : 2; op[i] = strcmp(name, "in") == 0 ? 'x' : strcmp(name, "if") == 0 ? 'i' : name[0]; for (int j = 0; j < cnt; j++) scanf("%d", &arg[i][j]); } scanf("%d", &q); for (int t = 0; t < q; t++) { for (int j = 0; j < m; j++) scanf("%d", &x[j]); int v; if (value(1, &v)) printf("%d\n", v); else puts("오류"); } return 0;}
Craykonmain.cray · 68 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];마디들 = [빈값];반복 (i = 1; i <= n; i++){ 마디들.넣기(콘솔.줄읽기().공백제거().나누기(" "));}q = 콘솔.줄읽기().수로변환();x = [];// 번호 마디의 값을 돌려준다. 계산할 수 없으면 빈값을 돌려준다// 함수 안에서 처음 넣은 이름(마디, 가, 다)은 부를 때마다 따로 생겨서 재귀해도 섞이지 않는다값(번호){ 마디 = 마디들[번호]; 만약 (마디[0] == "num") { 돌려주기 마디[1].수로변환(); } 만약 (마디[0] == "in") { 돌려주기 x[마디[1].수로변환() - 1]; } 가 = 값(마디[1].수로변환()); 만약 (가 == 빈값) { 돌려주기 빈값; // 빈값으로 계산하면 멈추니, 실패는 곧바로 위로 돌려보낸다 } 다 = 값(마디[2].수로변환()); 만약 (다 == 빈값) { 돌려주기 빈값; } 선택 (마디[0]) { 경우 "add": 돌려주기 가 + 다; 경우 "sub": 돌려주기 가 - 다; 경우 "div": 만약 (다 == 0) { 돌려주기 빈값; } 돌려주기 수학.몫(가, 다); // 0 쪽으로 버리는 몫 그밖에: // if: 고른 쪽 하나만 계산한다 만약 (가 < 다) { 돌려주기 값(마디[3].수로변환()); } 돌려주기 값(마디[4].수로변환()); }}반복 (t = 0; t < q; t++){ x = 콘솔.수들읽기(); v = 값(1); 만약 (v == 빈값) { 콘솔.쓰기("오류"); } 아니면 { 콘솔.쓰기(v); }}