1번 사람이 세상을 떠나며 M원을 남겼고, 이 돈을 집안의 나무를 따라 나눈다.
사람은 1번부터 n번까지 있고, 1번을 뺀 모든 사람은 꼭 한 사람의 자식이다. 모두 1번의 자손이다.
사람마다 살아 있는지(alive) 이미 떠났는지(dead)가 정해져 있고, 1번은 떠났다.
먼저 상속인이 될 수 있는 사람을 정한다. 살아 있는 사람은 상속인이 될 수 있다. 떠난 사람은 상속인이 될 수 있는 자식이 한 명이라도 있을 때만 상속인이 될 수 있다.
어떤 사람 p에게 돈 X원이 오면, p의 자식 가운데 상속인이 될 수 있는 사람들에게만 나눈다. 그런 자식이 c명이면 한 명마다 X를 c로 나눈 몫만큼 받고, 나머지 r원은 그 c명 가운데 맏이부터 r명이 1원씩 더 받는다.
몫을 받은 자식이 살아 있으면 그 돈을 갖는다. 떠난 자식이면 그 몫은 같은 규칙으로 그 자식의 자식들에게 내려간다.
1번의 M원으로 이 일을 시작한다. 1번의 자식 가운데 상속인이 될 수 있는 사람이 없으면 M원은 모두 국고로 간다.
첫 줄에 n과 M, 다음 n줄에 1번부터 n번 사람이 차례로 "상태 k 자식1 … 자식k"로 주어진다. 값은 빈칸 하나로 나뉜다. 상태는 alive 또는 dead이고, 자식은 맏이부터 나이 차례로 적혀 있다(번호 차례와 다를 수 있다).
첫 줄에 1번부터 n번까지 사람마다 받아서 가진 돈을 빈칸 하나씩 띄워 출력하라. 떠난 사람과 돈을 받지 못한 사람은 0이다.
둘째 줄에 국고로 간 돈을 출력하라. 국고로 간 돈이 없으면 0이다. 금액은 쉼표 없이 숫자만 쓴다.
상속인인지 정하는 일과 돈을 내려보내는 일을 각각 재귀 함수로 만들어 보자.
입력
1 ≤ n ≤ 1,000, 0 ≤ M ≤ 1,000,000,000,000(정수). k는 0 이상이고, 1번을 뺀 모든 사람이 어떤 사람의 자식으로 꼭 한 번 나오며, 1번은 누구의 자식으로도 나오지 않는다. 1번의 상태는 dead다. 1번에서 가장 먼 사람까지의 세대 수는 1,000 이하다(한 줄로 이어진 집안도 있다)
출력
두 줄
예시 1 · stdin
7 101
dead 3 2 3 4
alive 0
dead 2 5 6
dead 1 7
alive 0
alive 0
dead 0
stdout
0 51 0 0 25 25 0
0
예시 2 · stdin
3 7
dead 2 2 3
dead 0
dead 0
stdout
0 0 0
7
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
집안 나무의 가지마다 같은 규칙이 되풀이되니, '이 사람 아래를 정하는' 재귀 함수 두 개로 풀려요. 하나는 아래에서부터 상속인인지 정하고(자식을 먼저 정한 뒤 자기를 정해요), 다른 하나는 위에서부터 몫을 내려보내요. 두 함수가 함께 쓰는 표(살아 있는지, 자식 목록, 받은 돈)는 Python·JS·TS는 바깥 변수, Java·C#·C는 정적 변수·전역 배열, C++는 전역 vector, 크레이콘은 본문 맨 바깥에서 만든 이름으로 둬요. 함정 다섯: ① 떠난 사람은 '자식이 있다'가 아니라 '상속인이 될 수 있는 자식이 있다'일 때만 상속인이에요. 자식도 손주도 모두 먼저 떠났으면 상속인이 아니고, 그 몫을 받지 않아요. 그래서 상속인인지 정하는 일도 재귀예요. ② 상속인을 정할 때 Python any(), JS·TS some(), C·C++·Java·C# ||는 처음 참에서 멈춰서, 뒤의 자식들을 정하지 않고 지나가요. 모든 자식을 먼저 정해 둔 뒤 결과를 모아요. ③ 나누는 수는 상속인이 될 수 있는 자식의 수예요. 자식 전체로 나누면 상속인이 아닌 자식의 몫이 사라져요. 나머지는 맏이부터 1원씩이에요. ④ 한 줄로 이어진 집안은 재귀가 1,000단계까지 들어가요. Python은 기본 재귀 한도가 1,000이라 sys.setrecursionlimit로 늘려야 해요. 다른 언어는 이 깊이면 괜찮고, 크레이콘도 약 3,000단계까지 불러요. ⑤ M은 10^12까지라 C·C++·Java·C#에서는 long long·long으로 받아요. int는 약 21억까지예요. Python int는 끝이 없고 JS·TS·크레이콘의 수는 2^53까지 정확해서 괜찮아요. 몫과 나머지는 Python divmod, JS·TS Math.floor(x / c)와 %, 크레이콘 수학.몫(x, c)와 %, 나머지 언어는 정수 /와 %예요(돈이 0 이상이라 버리는 방향은 상관없어요).
Pythonmain.py · 49 줄
import syssys.setrecursionlimit(10000) # 세대가 1,000까지 이어진다. 기본 한도(1,000)로는 모자란다lines = sys.stdin.read().split("\n")n, money = map(int, lines[0].split())alive = [False] * (n + 1)children = [[] for _ in range(n + 1)]for i in range(1, n + 1): p = lines[i].split() alive[i] = p[0] == "alive" children[i] = [int(c) for c in p[2:]]heir = [False] * (n + 1)def mark(p): """p가 상속인이 될 수 있는지 정한다. 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다.""" found = False for c in children[p]: if mark(c): # 자식을 모두 정해 두어야 하므로 any()로 일찍 멈추지 않는다 found = True heir[p] = alive[p] or found return heir[p]got = [0] * (n + 1)def share(p, amount): """p에게 온 amount를 p의 상속인 자식들에게 나눈다.""" heirs = [c for c in children[p] if heir[c]] each, rest = divmod(amount, len(heirs)) for i, c in enumerate(heirs): part = each + (1 if i < rest else 0) # 나머지는 맏이부터 1원씩 if alive[c]: got[c] += part else: share(c, part) # 먼저 떠난 자식의 몫은 그 자식들에게 내려간다mark(1)treasury = 0if any(heir[c] for c in children[1]): share(1, money)else: treasury = moneyprint(" ".join(map(str, got[1:])))print(treasury)
JavaScriptmain.js · 38 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, money] = lines[0].trim().split(" ").map(Number); // 10^12도 number(2^53까지 정확)로 충분하다const alive = [false];const children = [[]];for (let i = 1; i <= n; i++) { const p = lines[i].trim().split(" "); alive.push(p[0] === "alive"); children.push(p.slice(2).map(Number));}const heir = new Array(n + 1).fill(false);// p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다function mark(p) { let found = false; for (const c of children[p]) if (mark(c)) found = true; // some()은 일찍 멈춰서 뒤의 자식을 정하지 못한다 heir[p] = alive[p] || found; return heir[p];}const got = new Array(n + 1).fill(0);// p에게 온 amount를 p의 상속인 자식들에게 나눈다function share(p, amount) { const heirs = children[p].filter((c) => heir[c]); const each = Math.floor(amount / heirs.length); const rest = amount % heirs.length; heirs.forEach((c, i) => { const part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩 if (alive[c]) got[c] += part; else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 });}mark(1);let treasury = 0;if (children[1].some((c) => heir[c])) share(1, money);else treasury = money;console.log(got.slice(1).join(" "));console.log(String(treasury));
TypeScriptmain.ts · 40 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, money] = lines[0].trim().split(" ").map(Number); // 10^12도 number(2^53까지 정확)로 충분하다const alive: boolean[] = [false];const children: number[][] = [[]];for (let i = 1; i <= n; i++) { const p = lines[i].trim().split(" "); alive.push(p[0] === "alive"); children.push(p.slice(2).map(Number));}const heir: boolean[] = new Array<boolean>(n + 1).fill(false);// p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다function mark(p: number): boolean { let found = false; for (const c of children[p]) if (mark(c)) found = true; heir[p] = alive[p] || found; return heir[p];}const got: number[] = new Array<number>(n + 1).fill(0);// p에게 온 amount를 p의 상속인 자식들에게 나눈다function share(p: number, amount: number): void { const heirs = children[p].filter((c) => heir[c]); const each = Math.floor(amount / heirs.length); const rest = amount % heirs.length; heirs.forEach((c, i) => { const part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩 if (alive[c]) got[c] += part; else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 });}mark(1);let treasury = 0;if (children[1].some((c) => heir[c])) share(1, money);else treasury = money;console.log(got.slice(1).join(" "));console.log(String(treasury));
JavaMain.java · 59 줄
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;public class Main { static boolean[] alive, heir; static int[][] children; static long[] got; // p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다 static boolean mark(int p) { boolean found = false; for (int c : children[p]) if (mark(c)) found = true; heir[p] = alive[p] || found; return heir[p]; } // p에게 온 amount를 p의 상속인 자식들에게 나눈다 static void share(int p, long amount) { List<Integer> heirs = new ArrayList<>(); for (int c : children[p]) if (heir[c]) heirs.add(c); long each = amount / heirs.size(), rest = amount % heirs.size(); for (int i = 0; i < heirs.size(); i++) { int c = heirs.get(i); long part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩 if (alive[c]) got[c] += part; else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 } } public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int n = Integer.parseInt(first[0]); long money = Long.parseLong(first[1]); // 10^12는 int를 넘는다 alive = new boolean[n + 1]; heir = new boolean[n + 1]; children = new int[n + 1][]; got = new long[n + 1]; for (int i = 1; i <= n; i++) { String[] p = in.readLine().trim().split(" "); alive[i] = p[0].equals("alive"); int k = Integer.parseInt(p[1]); children[i] = new int[k]; for (int j = 0; j < k; j++) children[i][j] = Integer.parseInt(p[2 + j]); } mark(1); boolean anyHeir = false; for (int c : children[1]) if (heir[c]) anyHeir = true; long treasury = 0; if (anyHeir) share(1, money); else treasury = money; StringBuilder out = new StringBuilder(); for (int i = 1; i <= n; i++) out.append(i > 1 ? " " : "").append(got[i]); out.append('\n').append(treasury).append('\n'); System.out.print(out); }}
C#Main.cs · 57 줄
using System;using System.Collections.Generic;using System.Linq;class Program{ static bool[] alive = Array.Empty<bool>(), heir = Array.Empty<bool>(); static int[][] children = Array.Empty<int[]>(); static long[] got = Array.Empty<long>(); // p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다 static bool Mark(int p) { bool found = false; foreach (int c in children[p]) if (Mark(c)) found = true; heir[p] = alive[p] || found; return heir[p]; } // p에게 온 amount를 p의 상속인 자식들에게 나눈다 static void Share(int p, long amount) { List<int> heirs = children[p].Where(c => heir[c]).ToList(); long each = amount / heirs.Count, rest = amount % heirs.Count; for (int i = 0; i < heirs.Count; i++) { int c = heirs[i]; long part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩 if (alive[c]) got[c] += part; else Share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 } } static void Main() { string[] first = Console.ReadLine()!.Trim().Split(' '); int n = int.Parse(first[0]); long money = long.Parse(first[1]); // 10^12는 int를 넘는다 alive = new bool[n + 1]; heir = new bool[n + 1]; children = new int[n + 1][]; children[0] = Array.Empty<int>(); got = new long[n + 1]; for (int i = 1; i <= n; i++) { string[] p = Console.ReadLine()!.Trim().Split(' '); alive[i] = p[0] == "alive"; children[i] = p.Skip(2).Select(int.Parse).ToArray(); } Mark(1); long treasury = 0; if (children[1].Any(c => heir[c])) Share(1, money); else treasury = money; Console.WriteLine(string.Join(" ", got.Skip(1))); Console.WriteLine(treasury); }}
C++main.cpp · 59 줄
#include <iostream>#include <string>#include <vector>int n;std::vector<bool> alive, heir;std::vector<std::vector<int>> children;std::vector<long long> got; // 10^12는 int를 넘는다// p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다bool mark(int p) { bool found = false; for (int c : children[p]) if (mark(c)) found = true; // ||로 이으면 짧은 계산 때문에 뒤의 자식을 정하지 못한다 heir[p] = alive[p] || found; return heir[p];}// p에게 온 amount를 p의 상속인 자식들에게 나눈다void share(int p, long long amount) { std::vector<int> heirs; for (int c : children[p]) if (heir[c]) heirs.push_back(c); long long count = static_cast<long long>(heirs.size()); long long each = amount / count, rest = amount % count; for (long long i = 0; i < count; i++) { int c = heirs[i]; long long part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩 if (alive[c]) got[c] += part; else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 }}int main() { std::ios::sync_with_stdio(false); long long money; std::cin >> n >> money; alive.assign(n + 1, false); heir.assign(n + 1, false); children.assign(n + 1, {}); got.assign(n + 1, 0); for (int i = 1; i <= n; i++) { std::string st; int k; std::cin >> st >> k; alive[i] = st == "alive"; children[i].resize(k); for (int& c : children[i]) std::cin >> c; } mark(1); bool anyHeir = false; for (int c : children[1]) if (heir[c]) anyHeir = true; long long treasury = 0; if (anyHeir) share(1, money); else treasury = money; for (int i = 1; i <= n; i++) std::cout << (i > 1 ? " " : "") << got[i]; std::cout << '\n' << treasury << '\n';}
Cmain.c · 58 줄
#include <stdio.h>#include <string.h>#define MAXN 1001static int alive[MAXN], heir[MAXN];static int kidStart[MAXN], kidCount[MAXN], kids[MAXN]; /* p의 자식은 kids[kidStart[p]]부터 kidCount[p]개 */static long long got[MAXN]; /* 10^12는 int를 넘는다 *//* p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다 */static int mark(int p) { int found = 0; for (int j = 0; j < kidCount[p]; j++) if (mark(kids[kidStart[p] + j])) found = 1; heir[p] = alive[p] || found; return heir[p];}/* p에게 온 amount를 p의 상속인 자식들에게 나눈다 */static void share(int p, long long amount) { int count = 0; for (int j = 0; j < kidCount[p]; j++) if (heir[kids[kidStart[p] + j]]) count++; long long each = amount / count, rest = amount % count; int i = 0; for (int j = 0; j < kidCount[p]; j++) { int c = kids[kidStart[p] + j]; if (!heir[c]) continue; long long part = each + (i < rest ? 1 : 0); /* 나머지는 맏이부터 1원씩 */ i++; if (alive[c]) got[c] += part; else share(c, part); /* 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 */ }}int main(void) { int n; long long money; scanf("%d %lld", &n, &money); int used = 0; for (int i = 1; i <= n; i++) { char st[8]; scanf("%7s %d", st, &kidCount[i]); alive[i] = strcmp(st, "alive") == 0; kidStart[i] = used; for (int j = 0; j < kidCount[i]; j++) scanf("%d", &kids[used++]); } mark(1); int anyHeir = 0; for (int j = 0; j < kidCount[1]; j++) if (heir[kids[kidStart[1] + j]]) anyHeir = 1; long long treasury = 0; if (anyHeir) share(1, money); else treasury = money; for (int i = 1; i <= n; i++) printf(i > 1 ? " %lld" : "%lld", got[i]); printf("\n%lld\n", treasury); return 0;}
Craykonmain.cray · 89 줄
// 함수 안에서 쓰는 이름(p, c, found, amount, 상속자식, 몫, 나머지, part, j)은 아래 본문에서 쓰지 않는다:// 본문 맨 바깥에서 만든 이름(살아있음, 자식, 상속인, 받은돈)은 모든 호출이 함께 쓰는 하나가 된다// p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다정하기(p){ found = 거짓; 각각 (c 에서 자식[p]) { 만약 (정하기(c)) { found = 참; } } 상속인[p] = 살아있음[p] || found; 돌려주기 상속인[p];}// p에게 온 amount를 p의 상속인 자식들에게 나눈다나누어주기(p, amount){ 상속자식 = []; 각각 (c 에서 자식[p]) { 만약 (상속인[c]) { 상속자식.넣기(c); } } 몫 = 수학.몫(amount, 상속자식.개수); 나머지 = amount % 상속자식.개수; 반복 (j = 0; j < 상속자식.개수; j++) { c = 상속자식[j]; part = 몫; 만약 (j < 나머지) { part = 몫 + 1; } 만약 (살아있음[c]) { 받은돈[c] += part; } 아니면 { 나누어주기(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 } }}첫줄 = 콘솔.줄읽기().공백제거().나누기(" ");n = 첫줄[0].수로변환();돈 = 첫줄[1].수로변환(); // 10^12도 2^53 안이라 정확하다살아있음 = 새목록(n + 1, 거짓);자식 = [[]];상속인 = 새목록(n + 1, 거짓);받은돈 = 새목록(n + 1, 0);반복 (i = 1; i <= n; i++){ 칸 = 콘솔.줄읽기().공백제거().나누기(" "); 살아있음[i] = 칸[0] == "alive"; 목록 = []; 반복 (k = 2; k < 칸.개수; k++) { 목록.넣기(칸[k].수로변환()); } 자식.넣기(목록);}정하기(1);상속인있음 = 거짓;각각 (x 에서 자식[1]){ 만약 (상속인[x]) { 상속인있음 = 참; }}국고 = 0;만약 (상속인있음){ 나누어주기(1, 돈);}아니면{ 국고 = 돈;}받은돈.자리빼기(0);콘솔.쓰기(받은돈.잇기(" "));콘솔.쓰기(국고);