이웃하지 않게 고른 마을의 최대 인구
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
0번부터 N - 1번까지 N개의 마을이 N - 1개의 도로로 연결되어 있고, 어느 두 마을 사이든 도로를 따라 가는 길이 정확히 하나 있습니다(트리).
people[i]는 i번 마을의 인구이고, roads[j] = [a, b]는 a번과 b번 마을이 도로로 바로 이어져 있다는 뜻입니다.
축제를 열 마을을 고르려고 합니다. 단, 도로로 바로 이어진 두 마을을 함께 고를 수는 없습니다. 고른 마을의 인구 합으로 가능한 최댓값을 반환하세요.
입출력 예
| people | roads | result |
|---|---|---|
[10, 1, 1, 1] | [[0, 1], [0, 2], [0, 3]] | 10 |
[1, 5, 5, 5] | [[0, 1], [0, 2], [0, 3]] | 15 |
[3, 2, 1, 10, 1] | [[0, 1], [1, 2], [2, 3], [3, 4]] | 13 |
입출력 예 설명
예 1 — 0번 마을 하나만 고르는 10이 가장 큽니다.
예 2 — 0번 마을 대신 1, 2, 3번 마을을 모두 고르면 15입니다.
예 3 — 일렬로 이어진 마을에서 0번(3)과 3번(10)을 고르면 13입니다. 2번과 3번은 이웃이라 함께 고를 수 없습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(people: int[], roads: int[][]) → long
제한 사항
-
people.length,people[i] roads.length,a,b,ab- 주어진 도로는 모든 마을을 하나의 트리로 잇습니다.
- 답은 32비트 정수를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| people | roads | 기대 출력 |
|---|---|---|
[10,1,1,1] | [[0,1],[0,2],[0,3]] | 10 |
[1,5,5,5] | [[0,1],[0,2],[0,3]] | 15 |
[3,2,1,10,1] | [[0,1],[1,2],[2,3],[3,4]] | 13 |
힌트
힌트
아무 마을(예: 0번)을 뿌리로 정하고, 마을마다 두 값을 계산합니다.
take[v]:v를 고를 때v의 서브트리에서 얻는 최대 인구skip[v]:v를 고르지 않을 때의 최대 인구
v를 고르면 자식은 고를 수 없고, 고르지 않으면 자식은 자유롭게 정할 수 있으므로
입니다. 답은 max(take[root], skip[root])입니다. 자식을 먼저 계산해야 하므로 DFS 후위 순서로 처리하세요.
마을이 일렬로 이어지면 깊이가 20만이 되므로, 재귀 대신 스택이나 BFS 순서를 거꾸로 도는 방법이 안전합니다.
복잡도 목표
마을마다 도로 목록 전체를 훑어 이웃을 찾는 풀이는 효율성 테스트에서 시간 초과가 납니다. 인접 리스트로 에 푸세요.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 230 ms | 추정 |
| C++ (GCC, gnu++23) | 230 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1568 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1460 ms | 추정 |
| C# 14 (.NET 10) | 1460 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |