건물에 차단기 n개가 있고 1번부터 n번까지 번호가 붙어 있다.
차단기 사이는 전선 n − 1개로 이어져 있고, 전선 하나 "a b"는 a번 차단기와 b번 차단기를 잇는다.
전선을 따라가면 어느 차단기에서든 다른 모든 차단기로 갈 수 있다.
1번 차단기가 발전소와 이어진 맨 위 차단기다.
전선으로 이어진 두 차단기 가운데 1번 차단기에 더 가까운 쪽이 '위 차단기', 다른 쪽이 '아래 차단기'다. 입력의 a와 b 가운데 어느 쪽이 위인지는 정해져 있지 않다.
i번 차단기에는 전기를 uᵢ만큼 쓰는 기기가 달려 있고, 차단기의 용량은 cᵢ다.
i번 차단기를 지나는 전기의 양 Lᵢ는, uᵢ에, i번 차단기와 전선으로 바로 이어진 아래 차단기 가운데 내려가지 않은 것들의 L을 모두 더한 값이다.
Lᵢ가 cᵢ보다 크면 i번 차단기는 내려간다. Lᵢ가 cᵢ와 같으면 내려가지 않는다.
내려간 차단기의 L은 위 차단기의 L에 더하지 않는다. 그래서 내려가는지는 맨 아래 차단기부터 차례로 정해진다.
어떤 차단기에 전기가 오려면, 그 차단기도, 그 차단기에서 1번 차단기까지 가는 길에 있는 차단기도 모두 내려가지 않아야 한다.
관리인은 1번 차단기에서 시작해 다음과 같이 차단기를 살핀다.
지금 차단기가 내려가 있으면 그 번호를 적고, 그 아래로는 가지 않는다.
내려가 있지 않으면 아래 차단기를 번호가 작은 것부터 하나씩 살피는데, 하나를 고르면 그 아래를 같은 방법으로 모두 살핀 다음에 다음 아래 차단기로 넘어간다.
첫 줄에 전기가 오는 차단기의 수를 출력하라.
둘째 줄에 L₁을 출력하라. 1번 차단기가 내려가도 L₁은 위 규칙으로 구한 값이다.
셋째 줄에 관리인이 적은 번호를 적은 차례대로 빈칸 하나로 띄워 출력하라. 적은 번호가 없으면 -를 출력한다.
입력
첫 줄에 n, 둘째 줄에 u₁ … uₙ, 셋째 줄에 c₁ … cₙ, 다음 n − 1줄에 줄마다 a와 b가 주어진다. 한 줄의 수들은 빈칸 하나로 나뉜다. 1 ≤ n ≤ 9,000, 0 ≤ uᵢ ≤ 1,000,000,000, 0 ≤ cᵢ ≤ 10,000,000,000,000(10조), 1 ≤ a, b ≤ n, a ≠ b. 1번 차단기에서 어느 차단기까지든 전선 1,200개 이하로 갈 수 있다. 모두 정수다
출력
첫 줄에 전기가 오는 차단기의 수, 둘째 줄에 L₁(쉼표 없이 숫자만), 셋째 줄에 관리인이 적은 번호들 또는 -
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
깊이 우선 탐색(DFS)을 두 번 해요. 한 번은 아래까지 내려갔다가 올라오면서 L을 더하고(아래가 먼저 정해져야 하니까요), 한 번은 위에서 내려가며 전기가 오는 곳을 세요. 전선에 위아래가 적혀 있지 않으니 양쪽으로 이어 두고 '방금 온 곳'만 빼고 내려가요. 예제에서 7번이 내려가서(5 > 4) 3번의 L은 5 + 40 = 45이고, 44보다 커서 3번도 내려가요. 4번도 내려가서(30 > 25) 2번의 L은 10 + 20 = 30, 1번도 30이에요. 함정 하나: 내려간 차단기의 몫을 위에 더하면 2번이 60이 되어 내려가고 1번까지 내려가요. 함정 둘: 5번은 20 = 20이라 버텨요. >=로 쓰면 5번도 내려가요. 함정 셋: 관리인은 내려간 차단기 아래로 가지 않아요. 계속 내려가면 7번까지 적어서 4 3 7이 돼요. 함정 넷: 아래 차단기는 번호순이에요. 입력 차례대로 보면 3 4가 돼요. JS·TS의 sort()는 비교 함수를 안 주면 문자열로 견줘서 10이 9보다 앞에 오니 sort((x, y) => x - y)로 써요. Python list.sort(), Java Collections.sort, C# List.Sort(), C++ std::sort, C qsort, 크레이콘 목록.정렬()은 수를 크기로 견줘요. 함정 다섯: L은 9조까지 커져요. Java·C#의 int는 오류 없이 엉뚱한 수가 되고 C·C++은 정의되지 않은 동작이라 long·long long을 써요. Python은 한계가 없고 JS·TS·크레이콘은 2^53까지 정확해요. 함정 여섯: 재귀 깊이예요. Python은 기본 한도가 1,000이라 깊이 1,200짜리 입력에서 RecursionError로 멈추니 sys.setrecursionlimit으로 올리거나 스택을 직접 써요. 다른 언어는 이 깊이면 괜찮지만 한도가 없는 것은 아니에요(크레이콘은 수천 단계). 크레이콘 함수는 전기량(v, 위) { … 돌려주기 total; }처럼 이름과 괄호로 바로 만들어요.
Pythonmain.py · 55 줄
import syssys.setrecursionlimit(5000) # 기본 한도 1,000으로는 깊이 1,200까지 못 내려간다def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) use = [0] + [int(x) for x in data[1:1 + n]] cap = [0] + [int(x) for x in data[1 + n:1 + 2 * n]] near = [[] for _ in range(n + 1)] # 전선은 방향 없이 주어진다 pos = 1 + 2 * n for _ in range(n - 1): a, b = int(data[pos]), int(data[pos + 1]) pos += 2 near[a].append(b) near[b].append(a) for v in range(1, n + 1): near[v].sort() # 번호가 작은 아래쪽 차단기부터 본다 tripped = [False] * (n + 1) def load(v, parent): """v를 지나는 전기의 양을 돌려준다. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다.""" total = use[v] for w in near[v]: if w != parent: below = load(w, v) if not tripped[w]: # 내려간 차단기 아래로는 전기가 흐르지 않는다 total += below tripped[v] = total > cap[v] return total lit = 0 fix = [] def walk(v, parent): """1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다.""" nonlocal lit if tripped[v]: fix.append(v) # 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return lit += 1 for w in near[v]: if w != parent: walk(w, v) root_load = load(1, 0) walk(1, 0) print(lit) print(root_load) print(" ".join(map(str, fix)) if fix else "-")main()
JavaScriptmain.js · 54 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const use = [0];const cap = [0];for (let v = 1; v <= n; v++) { use.push(data[v]); cap.push(data[n + v]);}// 전선은 방향 없이 주어진다const near = Array.from({ length: n + 1 }, () => []);for (let i = 0; i < n - 1; i++) { const a = data[1 + 2 * n + 2 * i]; const b = data[2 + 2 * n + 2 * i]; near[a].push(b); near[b].push(a);}// 번호가 작은 아래쪽 차단기부터 본다. sort()는 그냥 쓰면 문자열로 견주니 비교 함수를 준다for (const list of near) list.sort((x, y) => x - y);const tripped = new Array(n + 1).fill(false);// v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다function load(v, parent) { let total = use[v]; // 9조까지 커져도 2^53 안이라 정확하다 for (const w of near[v]) { if (w !== parent) { const below = load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total;}let lit = 0;const fix = [];// 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다function walk(v, parent) { if (tripped[v]) { fix.push(v); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; for (const w of near[v]) { if (w !== parent) walk(w, v); }}const rootLoad = load(1, 0);walk(1, 0);console.log(lit);console.log(rootLoad);console.log(fix.length > 0 ? fix.join(" ") : "-");
TypeScriptmain.ts · 56 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const use: number[] = [0];const cap: number[] = [0];for (let v = 1; v <= n; v++) { use.push(data[v]); cap.push(data[n + v]);}// 전선은 방향 없이 주어진다const near: number[][] = Array.from({ length: n + 1 }, (): number[] => []);for (let i = 0; i < n - 1; i++) { const a = data[1 + 2 * n + 2 * i]; const b = data[2 + 2 * n + 2 * i]; near[a].push(b); near[b].push(a);}// 번호가 작은 아래쪽 차단기부터 본다. sort()는 그냥 쓰면 문자열로 견주니 비교 함수를 준다for (const list of near) list.sort((x, y) => x - y);const tripped: boolean[] = new Array<boolean>(n + 1).fill(false);// v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다function load(v: number, parent: number): number { let total = use[v]; // 9조까지 커져도 2^53 안이라 정확하다 for (const w of near[v]) { if (w !== parent) { const below = load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total;}let lit = 0;const fix: number[] = [];// 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다function walk(v: number, parent: number): void { if (tripped[v]) { fix.push(v); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; for (const w of near[v]) { if (w !== parent) walk(w, v); }}const rootLoad = load(1, 0);walk(1, 0);console.log(lit);console.log(rootLoad);console.log(fix.length > 0 ? fix.join(" ") : "-");
JavaMain.java · 62 줄
import java.io.*;import java.util.*;public class Main { static long[] use, cap; static List<List<Integer>> near = new ArrayList<>(); static boolean[] tripped; static int lit = 0; static StringBuilder fix = new StringBuilder(); // v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다 static long load(int v, int parent) { long total = use[v]; // 합이 9조까지 커지므로 int로는 모자란다 for (int w : near.get(v)) { if (w != parent) { long below = load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total; } // 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다 static void walk(int v, int parent) { if (tripped[v]) { if (fix.length() > 0) fix.append(' '); fix.append(v); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; for (int w : near.get(v)) { if (w != parent) walk(w, v); } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); use = new long[n + 1]; cap = new long[n + 1]; tripped = new boolean[n + 1]; StringTokenizer st = new StringTokenizer(br.readLine()); for (int v = 1; v <= n; v++) use[v] = Long.parseLong(st.nextToken()); st = new StringTokenizer(br.readLine()); for (int v = 1; v <= n; v++) cap[v] = Long.parseLong(st.nextToken()); // 용량은 10조까지라 long으로 읽는다 for (int v = 0; v <= n; v++) near.add(new ArrayList<>()); for (int i = 0; i < n - 1; i++) { // 전선은 방향 없이 주어진다 st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken()); near.get(a).add(b); near.get(b).add(a); } for (List<Integer> list : near) Collections.sort(list); // 번호가 작은 아래쪽 차단기부터 본다 long rootLoad = load(1, 0); walk(1, 0); System.out.println(lit); System.out.println(rootLoad); System.out.println(fix.length() > 0 ? fix.toString() : "-"); }}
C#Main.cs · 71 줄
using System;using System.Collections.Generic;class Program{ static long[] use = Array.Empty<long>(), cap = Array.Empty<long>(); static List<int>[] near = Array.Empty<List<int>>(); static bool[] tripped = Array.Empty<bool>(); static int lit = 0; static readonly List<int> fix = new List<int>(); // v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다 static long Load(int v, int parent) { long total = use[v]; // 합이 9조까지 커지므로 int로는 모자란다 foreach (int w in near[v]) { if (w != parent) { long below = Load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total; } // 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다 static void Walk(int v, int parent) { if (tripped[v]) { fix.Add(v); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; foreach (int w in near[v]) { if (w != parent) Walk(w, v); } } static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]); use = new long[n + 1]; cap = new long[n + 1]; tripped = new bool[n + 1]; near = new List<int>[n + 1]; for (int v = 0; v <= n; v++) near[v] = new List<int>(); for (int v = 1; v <= n; v++) { use[v] = long.Parse(data[v]); cap[v] = long.Parse(data[n + v]); // 용량은 10조까지라 long으로 읽는다 } for (int i = 0; i < n - 1; i++) // 전선은 방향 없이 주어진다 { int a = int.Parse(data[1 + 2 * n + 2 * i]), b = int.Parse(data[2 + 2 * n + 2 * i]); near[a].Add(b); near[b].Add(a); } foreach (var list in near) list.Sort(); // 번호가 작은 아래쪽 차단기부터 본다 long rootLoad = Load(1, 0); Walk(1, 0); Console.WriteLine(lit); Console.WriteLine(rootLoad); Console.WriteLine(fix.Count > 0 ? string.Join(" ", fix) : "-"); }}
C++main.cpp · 65 줄
#include <algorithm>#include <iostream>#include <vector>using namespace std;vector<long long> use, cap;vector<vector<int>> near_; // near_[v] = v와 전선으로 이어진 차단기들vector<bool> tripped;int lit = 0;vector<int> fix;// v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다long long load(int v, int parent) { long long total = use[v]; // 합이 9조까지 커지므로 int로는 모자란다 for (int w : near_[v]) { if (w != parent) { long long below = load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total;}// 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다void walk(int v, int parent) { if (tripped[v]) { fix.push_back(v); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; for (int w : near_[v]) { if (w != parent) walk(w, v); }}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; use.assign(n + 1, 0); cap.assign(n + 1, 0); for (int v = 1; v <= n; v++) cin >> use[v]; for (int v = 1; v <= n; v++) cin >> cap[v]; near_.assign(n + 1, {}); for (int i = 0; i < n - 1; i++) { // 전선은 방향 없이 주어진다 int a, b; cin >> a >> b; near_[a].push_back(b); near_[b].push_back(a); } for (auto &list : near_) sort(list.begin(), list.end()); // 번호가 작은 아래쪽 차단기부터 본다 tripped.assign(n + 1, false); long long rootLoad = load(1, 0); walk(1, 0); cout << lit << "\n" << rootLoad << "\n"; if (fix.empty()) { cout << "-\n"; } else { for (size_t i = 0; i < fix.size(); i++) cout << fix[i] << (i + 1 < fix.size() ? ' ' : '\n'); } return 0;}
Cmain.c · 81 줄
#include <stdio.h>#include <stdlib.h>static long long *use, *cap;static int *start, *near; // near[start[v]] … near[start[v + 1] - 1] = v와 전선으로 이어진 차단기들static char *tripped;static int lit = 0;static int *fix, fixCount = 0;static int byNumber(const void *x, const void *y) { return *(const int *)x - *(const int *)y;}// v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다static long long load(int v, int parent) { long long total = use[v]; // 합이 9조까지 커지므로 int로는 모자란다 for (int i = start[v]; i < start[v + 1]; i++) { int w = near[i]; if (w != parent) { long long below = load(w, v); if (!tripped[w]) total += below; // 내려간 차단기 아래로는 전기가 흐르지 않는다 } } tripped[v] = total > cap[v]; return total;}// 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다static void walk(int v, int parent) { if (tripped[v]) { fix[fixCount++] = v; // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 return; } lit++; for (int i = start[v]; i < start[v + 1]; i++) { if (near[i] != parent) walk(near[i], v); }}int main(void) { int n; if (scanf("%d", &n) != 1) return 0; use = malloc((n + 1) * sizeof(long long)); cap = malloc((n + 1) * sizeof(long long)); for (int v = 1; v <= n; v++) scanf("%lld", &use[v]); for (int v = 1; v <= n; v++) scanf("%lld", &cap[v]); // 용량은 10조까지라 %lld로 읽는다 // 전선은 방향 없이 주어진다. 먼저 차단기마다 전선 수를 세어 자리를 잡고, 그 자리에 채운다 int edges = n - 1; int *a = malloc((edges + 1) * sizeof(int)), *b = malloc((edges + 1) * sizeof(int)); start = calloc(n + 2, sizeof(int)); for (int i = 0; i < edges; i++) { scanf("%d %d", &a[i], &b[i]); start[a[i] + 1]++; start[b[i] + 1]++; } for (int v = 1; v <= n + 1; v++) start[v] += start[v - 1]; near = malloc((2 * edges + 1) * sizeof(int)); int *fill = malloc((n + 2) * sizeof(int)); for (int v = 0; v <= n + 1; v++) fill[v] = start[v]; for (int i = 0; i < edges; i++) { near[fill[a[i]]++] = b[i]; near[fill[b[i]]++] = a[i]; } // 번호가 작은 아래쪽 차단기부터 본다 for (int v = 1; v <= n; v++) qsort(near + start[v], start[v + 1] - start[v], sizeof(int), byNumber); tripped = calloc(n + 1, 1); fix = malloc((n + 1) * sizeof(int)); long long rootLoad = load(1, 0); walk(1, 0); printf("%d\n%lld\n", lit, rootLoad); if (fixCount == 0) { printf("-\n"); } else { for (int i = 0; i < fixCount; i++) printf(i > 0 ? " %d" : "%d", fix[i]); printf("\n"); } free(use); free(cap); free(a); free(b); free(start); free(near); free(fill); free(tripped); free(fix); return 0;}
Craykonmain.cray · 72 줄
// v를 지나는 전기의 양. 아래쪽부터 정해야 하므로 내려갔다 올라오면서 더한다전기량(v, 위){ total = use[v]; // 9조까지 커져도 2^53 안이라 정확하다 각각 (w 에서 near[v]) { 만약 (w != 위) { below = 전기량(w, v); 만약 (!tripped[w]) { total += below; } } } tripped[v] = total > cap[v]; 돌려주기 total;}// 1번에서 내려가며 전기가 오는 곳을 세고, 맨 먼저 올릴 차단기를 적는다걷기(v, 위){ 만약 (tripped[v]) { fix.넣기(v + 1); // 이 아래는 어차피 전기가 안 오니 내려가지 않는다 돌려주기; } lit += 1; 각각 (w 에서 near[v]) { 만약 (w != 위) { 걷기(w, v); } }}n = 콘솔.줄읽기().수로변환();// 목록은 10,000칸까지라 차단기 번호에서 1을 빼 0번부터 둔다use = 콘솔.수들읽기();cap = 콘솔.수들읽기();near = [];반복 (v = 0; v < n; v++){ near.넣기([]);}반복 (i = 0; i < n - 1; i++){ 선 = 콘솔.수들읽기(); near[선[0] - 1].넣기(선[1] - 1); near[선[1] - 1].넣기(선[0] - 1);}각각 (list 에서 near){ list.정렬(); // 번호가 작은 아래쪽 차단기부터 본다}tripped = 새목록(n, 거짓);lit = 0;fix = [];rootLoad = 전기량(0, -1);걷기(0, -1);콘솔.쓰기(lit);콘솔.쓰기(rootLoad);만약 (fix.개수 > 0){ 콘솔.쓰기(fix);}아니면{ 콘솔.쓰기("-");}