21853번 - 도로 폐쇄 서브태스크다국어언어 제한함수 구현
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 43 | 14 | 12 | 35.294% |
문제
수라바야 시는 N개의 분기점이 있는데, 0부터 $N - 1$로 번호가 매겨져 있다. 이 분기점들은 $N - 1$개의 양방향 도로로 연결되어 있고, 0부터 $N - 2$로 번호가 매겨져 있다. 서로 다른 두 분기점을 어떻게 고르더라도 이 둘을 잇는 유일한 경로가 있다. 도로 $i$ ($0 \le i \le N - 2$)는 분기점 $U[i]$와 $V[i]$를 연결한다.
환경 문제에 대한 경각심을 높이기 위해서 수라바야 시의 시장 김 박사는 자동차 없는 날을 지정하려고 한다. 자동차 없는 날 행사로, 김 박사는 도로를 폐쇄하려고 한다. 폐쇄할 도로는 다음과 같이 정해진다. 김 박사는 먼저 음이 아닌 정수 $k$를 고르고, 모든 분기점에 $k$개 이하의 폐쇄되지 않은 도로가 직접 연결되어 있도록 한다. 도로 $i$를 폐쇄하는 비용은 $W[i]$이다.
김 박사를 도와서 가능한 음이 아닌 정수 $k$ ($0 \le k \le N - 1$) 각각에 대해 조건을 만족하게 도로를 폐쇄하는 최소 비용을 구하자.
구현
다음 함수를 구현해야 한다.
int64[] minimum_closure_costs(int N, int[] U, int[] V, int[] W)
- $N$: 수라바야의 분기점 수
- $U$, $V$ : 길이 $N - 1$인 배열로, 분기점 $U[i]$와 $V[i]$는 도로 $i$로 연결되어 있다.
- $W$: 길이 $N - 1$인 배열로, $W[i]$는 도로 $i$를 폐쇄하는데 드는 비용이다.
- 이 함수는 하나의 배열 $N$을 리턴해야 한다. 각각 $k$마다 ($0 \le k \le N - 1$), 이 배열의 $k$번째 원소는 모든 분기점이 직접 연결된 폐쇄되지 않은 도로가 최대 $k$개가 되도록 도로를 폐쇄하는 최소 비용이다.
- 이 함수는 정확하게 한 번 호출된다.
예제 1
다음 호출을 생각해보자.
minimum_closure_costs(5, [0, 0, 0, 2], [1, 2, 3, 4], [1, 4, 3, 2])
이는 총 5개의 분기점이 있고, 이를 잇는 도로 4개가 (0, 1), (0, 2), (0, 3), (2, 4)을 잇고, 이 도로를 폐쇄하는 비용은 각각 1, 4, 3, 2라는 뜻이다.
최소 비용을 구하기 위해서는 다음과 같다.
- 김 박사가 $k = 0$으로 고르면, 모든 도로가 폐쇄되어야 하므로 총 비용은 1 + 4 + 3 + 2 = 10이다.
- 김 박사가 $k = 1$로 고르면, 도로 0과 도로 1을 폐쇄하면 총 비용 1 + 4 = 5가 된다.
- 김 박사가 $k = 2$로 고르면, 도로 0을 폐쇄하면 총 비용 1이 된다.
- 김 박사가 $k = 3$ 또는 $k = 4$를 고르면, 어느 도로도 폐쇄하지 않아도 된다.
따라서, minimum_closure_costs의 리턴값은 [10, 5, 1, 0, 0]이다.
예제 2
다음 호출을 생각해 보자.
minimum_closure_costs(4, [0, 2, 0], [1, 0, 3], [5, 10, 5])
이는 총 4개의 분기점이 있고, 이를 잇는 도로 3개가 (0, 1), (2, 0), (0, 3)을 잇고, 이 도로를 폐쇄하는 비용은 각각 5, 10, 5라는 뜻이다.
최소 비용을 구하기 위해서는 다음과 같다.
- 김 박사가 $k = 0$으로 고르면, 모든 도로가 폐쇄되어야 하므로 총 비용은 5 + 10 + 5 = 20이다.
- 김 박사가 $k = 1$로 고르면, 도로 0과 도로 2을 폐쇄하면 총 비용 5 + 5 = 10이 된다.
- 김 박사가 $k = 2$로 고르면, 도로 0 또는 도로 2을 폐쇄하면 총 비용 5가 된다.
- 김 박사가 $k = 3$을 고르면, 어느 도로도 폐쇄하지 않아도 된다.
따라서, minimum_closure_costs의 리턴값은 [20, 10, 5, 0]이다.
제한
- $2 \le N \le 100\,000$
- $0 \le U[i], V[i] \le N - 1$ (모든 $0 \le i \le N - 2$)
- 어떤 두 분기점도 하나 또는 그 이상의 도로를 통해서 연결되어 있다.
- $1 \le W[i] \le 10^9$ (모든 $0 \le i \le N - 2$)
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $U[i] = 0$ (모든 $0 \le i \le N - 2$) |
| 2 | 7 | $U[i] = i$, $V[i] = i + 1$ (모든 $0 \le i \le N - 2$) |
| 3 | 14 | $N \le 200$ |
| 4 | 10 | $N \le 2000$ |
| 5 | 17 | $W[i] = 1$ (모든 $0 \le i \le N - 2$) |
| 6 | 25 | $W[i] \le 10$ (모든 $0 \le i \le N - 2$) |
| 7 | 22 | 추가적인 제약 조건이 없다. |
샘플 그레이더
샘플 그레이더는 입력을 다음 양식으로 읽는다.
- line 1: $N$
- line 2 + $i$ ($0 \le i \le N - 2$): $U[i]$ $V[i]$ $W[i]$
샘플 그레이더는 minimum_closure_costs가 리턴한 배열을 한 줄에 출력한다.
첨부
제출할 수 있는 언어
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호