https://www.acmicpc.net/problem/26972
문제 요약
트리가 주어진다. 각 정점에 건초 수가 주어진다. 건초는 인접한 정점으로 한 번에 원하는 만큼 옮길 수 있다. 건초를 옮기는 횟수를 최소로 해서 모든 정점의 건초 수가 같게 만들어라.
풀이 (N)
- 트리DP
각 정점의 건초 수를 평균으로 맞춰야 한다. 건초를 옮겨야 하는 정점은 정해져 있고(평균이 아닌 정점) 트리에서 경로는 유일하기 때문에 횟수는 중요한게 아니고 어떻게 옮길지만 생각하면 된다. 각 서브트리의 전체 건초 수가 정해져 있기 때문에 남는건 루트로 올리고 부족한 건 루트에서 받아오면 된다. 과정중에 건초가 -개가 되면 안되니까 올리는 과정을 먼저하고 내리는 과정을 나중에 해줘야 한다.
'풀이' 카테고리의 다른 글
[백준] 11211 - Count von Walken’s Fence (c++) (0) | 2025.01.16 |
---|---|
[백준] 19671 - Lasers (c++) (0) | 2025.01.16 |
[백준] 15859 - Citations (c++) (0) | 2025.01.16 |
[백준] 17353 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 (c++) (0) | 2025.01.15 |
[백준] 23044 - 트리 조각하기 (c++) (0) | 2025.01.14 |