계산표에 칸 n개가 있고, 칸마다 이름과 식이 하나씩 있다.
한 줄은 "이름 = 항 + 항 + … + 항" 꼴이고, 낱말 사이는 빈칸 하나로 나뉜다.
항은 0 이상의 정수이거나 어느 칸(자기 자신일 수도 있다)의 이름이다.
칸의 값은 식에 적힌 항들의 값을 모두 더한 것이고, 같은 이름이 식에 여러 번 나오면 나온 만큼 더한다.
식을 따라가다 보면 다시 처음 칸으로 돌아오는 칸, 곧 고리에 든 칸은 값을 정할 수 없다.
고리에 든 칸을 식에 쓰는 칸도, 그런 칸을 쓰는 칸도 값을 정할 수 없다(몇 단계를 거쳐도 마찬가지다).
입력에 적힌 차례대로 칸마다 한 줄에 "이름 값"을 출력하라.
값을 정할 수 없는 칸은 값 대신 ERR을 출력한다.
입력
첫 줄에 n, 다음 n줄에 칸이 하나씩 주어진다. 1 ≤ n ≤ 5,000. 이름은 영어 소문자로 시작하고 영어 소문자와 숫자로만 된 1~8글자이며 서로 다르다. 식의 항은 1~8개이고, 수는 0 이상 1,000,000 이하이며, 식에 나오는 이름은 모두 어느 칸의 이름이다. 모든 식에 나오는 이름 항은 모두 합쳐 10,000개 이하이다. 값을 정할 수 있는 칸의 값은 10^15 이하이다.
출력
n줄, 줄마다 "이름 값" 또는 "이름 ERR"
예시 1 · stdin
8
a = 3 + b + c
b = 10
c = b + b + 1
d = d + 1
e = a + f
f = e
g = d
h = a + 2
stdout
a 34
b 10
c 21
d ERR
e ERR
f ERR
g ERR
h 36
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
칸 j를 식에 쓰는 칸 i에 대해 화살표 j → i를 그으면, 값을 정할 수 있는 칸은 위상 정렬로 차례가 매겨지는 칸과 같아요. Kahn 알고리즘이 깔끔해요: 칸마다 '아직 값을 모르는 이름 항의 수'(waiting)를 세고, 0인 칸을 큐에 넣고, 꺼낸 칸의 값을 그 칸을 쓰는 칸들에 더하며 waiting을 하나씩 줄여요. 끝까지 큐에 못 들어간 칸이 바로 고리에 들었거나 고리에 매달린 칸이에요 — 고리를 따로 찾을 필요가 없어요. 함정 하나: 고리에 든 칸만 ERR로 하면 틀려요. 예시의 g는 고리 d를 쓰니 ERR이에요. 재귀로 따라가다 '계산하는 중'인 칸을 만났을 때 그 칸만 표시하고 0으로 치면, 고리를 쓰는 칸에 엉뚱한 수가 나와요. 함정 둘: b + b는 b를 두 번 더해요(예시의 c = 21). 이름을 집합(Set)에 모으면 한 번만 더해져요 — 기다림 수와 '쓰는 칸' 목록 모두 나온 만큼 넣어요. 함정 셋: 재귀로 식을 따라가면 5,000칸 사슬에서 5,000단계 깊이가 돼요. Python 기본 재귀 한도 1,000을 넘고, 크레이콘도 수천 단계에서 멈춰요. 큐를 쓰는 Kahn 알고리즘은 재귀가 없어서 이 걱정이 없어요. 함정 넷: 값은 10^15까지라 32비트 int(약 21억)를 넘어요(사슬 5,000칸 × 100만 = 50억, 두 배씩 커지는 사슬은 2^49). C·C++ long long, Java·C# long이 필요하고(C#·Java int는 조용히 음수로 감겨요), Python 정수는 끝이 없고, JavaScript·TypeScript·크레이콘의 수는 배정밀도 실수라 2^53(약 9×10^15)까지 정확해서 그대로 돼요. 이름 → 칸 번호는 사전으로 찾아요: Python dict, JavaScript·TypeScript Map, Java HashMap<String, Integer>, C# Dictionary<string, int>, C++ std::unordered_map<std::string, int>. C는 사전이 없어서 칸 번호를 이름 차례로 qsort해 두고 strcmp로 이분 탐색해요. 줄을 나누는 것도 달라요: 낱말 차례가 [이름, "=", 항, "+", 항, …]이라 Python w[2::2]처럼 두 칸씩 건너뛰면 항만 남아요. C는 fgets로 한 줄을 읽어 strtok으로 자르고, C++는 std::istringstream으로 낱말을 읽어요. 수인지 이름인지는 첫 글자가 숫자인지로 가려요(이름은 글자로 시작해요). 크레이콘은 사전()으로 이름 → 번호를 두고, 첫 글자는 글자.코드(w[k][0])가 48~57("0"~"9")인지로 가려요. 큐는 목록에 넣기만 하고 앞에서부터 읽는 자리(head)를 옮겨요.
Pythonmain.py · 44 줄
import sysfrom collections import dequelines = sys.stdin.read().split("\n")n = int(lines[0])names = []const = [] # const[i] = i번 칸 식에 적힌 수들의 합refs = [] # refs[i] = i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번)for line in lines[1 : 1 + n]: w = line.split() names.append(w[0]) c = 0 r = [] for term in w[2::2]: # w = [이름, "=", 항, "+", 항, "+", ...] if term[0].isdigit(): c += int(term) else: r.append(term) const.append(c) refs.append(r)index = {name: i for i, name in enumerate(names)}users = [[] for _ in range(n)] # users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼)waiting = [0] * n # 아직 값을 모르는, 식에 쓴 이름의 수for i in range(n): for name in refs[i]: users[index[name]].append(i) waiting[i] += 1# 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다value = const[:]known = [False] * nqueue = deque(i for i in range(n) if waiting[i] == 0)while queue: j = queue.popleft() known[j] = True for i in users[j]: value[i] += value[j] waiting[i] -= 1 if waiting[i] == 0: queue.append(i)# 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다print("\n".join(f"{names[i]} {value[i] if known[i] else 'ERR'}" for i in range(n)))
JavaScriptmain.js · 43 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const names = [];const value = []; // 처음엔 식에 적힌 수들의 합, 이름 칸의 값을 알게 될 때마다 더한다const refs = []; // refs[i] = i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번)for (let i = 1; i <= n; i++) { const w = lines[i].trim().split(" "); // [이름, "=", 항, "+", 항, ...] names.push(w[0]); let c = 0; const r = []; for (let k = 2; k < w.length; k += 2) { if (/^[0-9]/.test(w[k])) c += Number(w[k]); else r.push(w[k]); } value.push(c); refs.push(r);}const index = new Map(names.map((name, i) => [name, i]));const users = Array.from({ length: n }, () => []); // users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼)const waiting = new Array(n).fill(0); // 아직 값을 모르는, 식에 쓴 이름의 수refs.forEach((r, i) => { for (const name of r) { users[index.get(name)].push(i); waiting[i]++; }});// 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다const known = new Array(n).fill(false);const queue = [];for (let i = 0; i < n; i++) if (waiting[i] === 0) queue.push(i);for (let head = 0; head < queue.length; head++) { const j = queue[head]; known[j] = true; for (const i of users[j]) { value[i] += value[j]; // 10^15까지라 배정밀도 수로도 정확하다 if (--waiting[i] === 0) queue.push(i); }}// 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다console.log(names.map((name, i) => `${name} ${known[i] ? value[i] : "ERR"}`).join("\n"));
TypeScriptmain.ts · 45 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const names: string[] = [];const value: number[] = []; // 처음엔 식에 적힌 수들의 합, 이름 칸의 값을 알게 될 때마다 더한다const refs: string[][] = []; // refs[i] = i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번)for (let i = 1; i <= n; i++) { const w: string[] = lines[i].trim().split(" "); // [이름, "=", 항, "+", 항, ...] names.push(w[0]); let c = 0; const r: string[] = []; for (let k = 2; k < w.length; k += 2) { if (/^[0-9]/.test(w[k])) c += Number(w[k]); else r.push(w[k]); } value.push(c); refs.push(r);}const index = new Map<string, number>(names.map((name, i): [string, number] => [name, i]));const users: number[][] = Array.from({ length: n }, (): number[] => []); // users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼)const waiting: number[] = new Array<number>(n).fill(0); // 아직 값을 모르는, 식에 쓴 이름의 수refs.forEach((r, i) => { for (const name of r) { users[index.get(name)!].push(i); // 식에 쓴 이름은 모두 어느 줄에선가 정해진다 waiting[i]++; }});// 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다const known: boolean[] = new Array<boolean>(n).fill(false);const queue: number[] = [];for (let i = 0; i < n; i++) if (waiting[i] === 0) queue.push(i);for (let head = 0; head < queue.length; head++) { const j = queue[head]; known[j] = true; for (const i of users[j]) { value[i] += value[j]; // 10^15까지라 number로도 정확하다 if (--waiting[i] === 0) queue.push(i); }}// 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다console.log(names.map((name, i) => `${name} ${known[i] ? value[i] : "ERR"}`).join("\n"));
JavaMain.java · 63 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); String[] names = new String[n]; long[] value = new long[n]; // 처음엔 식에 적힌 수들의 합. 10^15까지라 long List<List<String>> refs = new ArrayList<>(); // i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번) Map<String, Integer> index = new HashMap<>(); for (int i = 0; i < n; i++) { String[] w = in.readLine().trim().split(" "); // [이름, "=", 항, "+", 항, ...] names[i] = w[0]; index.put(w[0], i); List<String> r = new ArrayList<>(); for (int k = 2; k < w.length; k += 2) { if (Character.isDigit(w[k].charAt(0))) value[i] += Long.parseLong(w[k]); else r.add(w[k]); } refs.add(r); } List<List<Integer>> users = new ArrayList<>(); // users.get(j) = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼) for (int i = 0; i < n; i++) users.add(new ArrayList<>()); int[] waiting = new int[n]; // 아직 값을 모르는, 식에 쓴 이름의 수 for (int i = 0; i < n; i++) { for (String name : refs.get(i)) { users.get(index.get(name)).add(i); waiting[i]++; } } // 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다 boolean[] known = new boolean[n]; ArrayDeque<Integer> queue = new ArrayDeque<>(); for (int i = 0; i < n; i++) if (waiting[i] == 0) queue.add(i); while (!queue.isEmpty()) { int j = queue.poll(); known[j] = true; for (int i : users.get(j)) { value[i] += value[j]; if (--waiting[i] == 0) queue.add(i); } } // 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다 StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) { out.append(names[i]).append(' '); if (known[i]) out.append(value[i]); else out.append("ERR"); out.append('\n'); } System.out.print(out); }}
C#Main.cs · 65 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); var names = new string[n]; var value = new long[n]; // 처음엔 식에 적힌 수들의 합. 10^15까지라 long var refs = new List<string>[n]; // i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번) var index = new Dictionary<string, int>(); for (int i = 0; i < n; i++) { string[] w = Console.ReadLine().Trim().Split(' '); // [이름, "=", 항, "+", 항, ...] names[i] = w[0]; index[w[0]] = i; refs[i] = new List<string>(); for (int k = 2; k < w.Length; k += 2) { if (char.IsDigit(w[k][0])) value[i] += long.Parse(w[k]); else refs[i].Add(w[k]); } } var users = new List<int>[n]; // users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼) for (int i = 0; i < n; i++) users[i] = new List<int>(); var waiting = new int[n]; // 아직 값을 모르는, 식에 쓴 이름의 수 for (int i = 0; i < n; i++) { foreach (string name in refs[i]) { users[index[name]].Add(i); waiting[i]++; } } // 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다 var known = new bool[n]; var queue = new Queue<int>(); for (int i = 0; i < n; i++) if (waiting[i] == 0) queue.Enqueue(i); while (queue.Count > 0) { int j = queue.Dequeue(); known[j] = true; foreach (int i in users[j]) { value[i] += value[j]; if (--waiting[i] == 0) queue.Enqueue(i); } } // 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다 var sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.Append(names[i]).Append(' '); if (known[i]) sb.Append(value[i]); else sb.Append("ERR"); sb.Append('\n'); } Console.Write(sb.ToString()); }}
C++main.cpp · 61 줄
#include <cctype>#include <iostream>#include <queue>#include <sstream>#include <string>#include <unordered_map>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::string line; std::getline(std::cin, line); int n = std::stoi(line); std::vector<std::string> names(n); std::vector<long long> value(n, 0); // 처음엔 식에 적힌 수들의 합. 10^15까지라 long long std::vector<std::vector<std::string>> refs(n); // i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번) std::unordered_map<std::string, int> index; for (int i = 0; i < n; i++) { std::getline(std::cin, line); std::istringstream words(line); std::string term, sign; words >> names[i] >> sign; // 이름, "=" index[names[i]] = i; while (words >> term) { if (std::isdigit(static_cast<unsigned char>(term[0]))) value[i] += std::stoll(term); else refs[i].push_back(term); words >> sign; // "+" (줄 끝이면 읽지 못하고 끝난다) } } std::vector<std::vector<int>> users(n); // users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼) std::vector<int> waiting(n, 0); // 아직 값을 모르는, 식에 쓴 이름의 수 for (int i = 0; i < n; i++) { for (const auto& name : refs[i]) { users[index[name]].push_back(i); waiting[i]++; } } // 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다 std::vector<bool> known(n, false); std::queue<int> queue; for (int i = 0; i < n; i++) if (waiting[i] == 0) queue.push(i); while (!queue.empty()) { int j = queue.front(); queue.pop(); known[j] = true; for (int i : users[j]) { value[i] += value[j]; if (--waiting[i] == 0) queue.push(i); } } // 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다 std::string out; for (int i = 0; i < n; i++) out += names[i] + " " + (known[i] ? std::to_string(value[i]) : "ERR") + "\n"; std::cout << out; return 0;}
Cmain.c · 90 줄
#include <ctype.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 5000#define MAXREF 10000static char names[MAXN][9];static long long value[MAXN]; /* 처음엔 식에 적힌 수들의 합. 10^15까지라 long long */static char refName[MAXREF][9]; /* 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번) */static int refOwner[MAXREF]; /* 그 이름을 쓴 칸 */static int nref;static int sorted[MAXN]; /* 칸 번호를 이름 차례로 늘어놓은 것: 이름 → 번호를 이진 탐색으로 찾는다 */static int byName(const void* a, const void* b) { return strcmp(names[*(const int*)a], names[*(const int*)b]);}static int findCell(const char* name, int n) { int lo = 0, hi = n - 1; while (lo <= hi) { int mid = (lo + hi) / 2; int c = strcmp(names[sorted[mid]], name); if (c == 0) return sorted[mid]; if (c < 0) lo = mid + 1; else hi = mid - 1; } return -1;}/* 같은 칸을 쓰는 칸들을 배열로 엮는다: head[j]에서 시작해 next[e]로 이어지고, user[e]가 쓰는 칸 */static int head[MAXN], next[MAXREF], user[MAXREF];static int waiting[MAXN]; /* 아직 값을 모르는, 식에 쓴 이름의 수 */static int known[MAXN];static int queue[MAXN];int main(void) { char line[256]; if (!fgets(line, sizeof line, stdin)) return 0; int n = atoi(line); for (int i = 0; i < n; i++) { fgets(line, sizeof line, stdin); char* word = strtok(line, " \r\n"); /* 이름 */ strcpy(names[i], word); strtok(NULL, " \r\n"); /* "=" */ while ((word = strtok(NULL, " \r\n")) != NULL) { if (strcmp(word, "+") == 0) continue; if (isdigit((unsigned char)word[0])) { value[i] += atoll(word); } else { strcpy(refName[nref], word); refOwner[nref++] = i; } } } for (int i = 0; i < n; i++) { sorted[i] = i; head[i] = -1; } qsort(sorted, n, sizeof sorted[0], byName); for (int e = 0; e < nref; e++) { int j = findCell(refName[e], n); user[e] = refOwner[e]; next[e] = head[j]; head[j] = e; waiting[refOwner[e]]++; } /* 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다 */ int qhead = 0, qtail = 0; for (int i = 0; i < n; i++) if (waiting[i] == 0) queue[qtail++] = i; while (qhead < qtail) { int j = queue[qhead++]; known[j] = 1; for (int e = head[j]; e != -1; e = next[e]) { int i = user[e]; value[i] += value[j]; if (--waiting[i] == 0) queue[qtail++] = i; } } /* 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다 */ for (int i = 0; i < n; i++) { if (known[i]) printf("%s %lld\n", names[i], value[i]); else printf("%s ERR\n", names[i]); } return 0;}
Craykonmain.cray · 80 줄
n = 콘솔.줄읽기().공백제거().수로변환();names = [];value = []; // 처음엔 식에 적힌 수들의 합, 이름 칸의 값을 알게 될 때마다 더한다refs = []; // refs[i] = i번 칸 식에 적힌 이름들(같은 이름이 두 번 나오면 두 번)index = 사전(); // 이름 → 칸 번호반복 (i = 0; i < n; i++){ w = 콘솔.줄읽기().공백제거().나누기(" "); // [이름, "=", 항, "+", 항, ...] names.넣기(w[0]); index[w[0]] = i; c = 0; r = []; 반복 (k = 2; k < w.개수; k += 2) { 첫글자 = 글자.코드(w[k][0]); 만약 (첫글자 >= 48 && 첫글자 <= 57) { c += w[k].수로변환(); } 아니면 { r.넣기(w[k]); } } value.넣기(c); refs.넣기(r);}users = []; // users[j] = j번 칸을 식에 쓰는 칸들(쓴 횟수만큼)반복 (i = 0; i < n; i++){ users.넣기([]);}waiting = 새목록(n, 0); // 아직 값을 모르는, 식에 쓴 이름의 수반복 (i = 0; i < n; i++){ 각각 (name 에서 refs[i]) { users[index[name]].넣기(i); waiting[i] += 1; }}// 위상 정렬(Kahn 알고리즘): 기다릴 것이 없는 칸부터 값을 정하고, 그 칸을 쓰는 칸의 기다림을 하나씩 줄인다known = 새목록(n, 거짓);queue = [];반복 (i = 0; i < n; i++){ 만약 (waiting[i] == 0) { queue.넣기(i); }}반복 (head = 0; head < queue.개수; head++){ j = queue[head]; known[j] = 참; 각각 (i 에서 users[j]) { value[i] += value[j]; waiting[i] -= 1; 만약 (waiting[i] == 0) { queue.넣기(i); } }}// 끝까지 기다림이 남은 칸은 고리에 들었거나 고리에 든 칸을 (거쳐서라도) 쓴다반복 (i = 0; i < n; i++){ 만약 (known[i]) { 콘솔.쓰기(names[i] + " " + value[i]); } 아니면 { 콘솔.쓰기(names[i] + " ERR"); }}