문제 링크(Link)
https://www.acmicpc.net/problem/1949
문제 해결(Solution)
Tree를 구현한 후, DP로 문제를 해결.
1. 주어지는 그래프 관계를 트리로 구현한다. 시간복잡도 O(N)이 소요된다.
2. DP[N][Q] : 마을 N에서 Q(0 : 우수 마을로 선정하지 않음, 1 : 우수 마을로 선정)일 때, 우수마을의 인원의 최대 합. 시간복잡도 O(N)이 소요된다.
3. 전체 시간 복잡도는 O(N)이 된다.
주의할 점 || 생각해볼 점(Caution || Consideration)
1. DP의 시간복잡도를 계산하는 것은 생각보다 어렵다. O(N)이라고 적었으나, 사실 그 보단 더욱 많은 시간이 소요된다.
참고(Reference)
-
※ 정확하고 부드러운 태클은 언제나 환영입니다.
'Problem Solving > DP' 카테고리의 다른 글
BOJ 14863 - 서울에서 경산까지 (0) | 2018.02.11 |
---|---|
BOJ 12841 - 정보대 등산 (0) | 2018.01.15 |
BOJ 1103 - 게임 (0) | 2017.10.30 |
BOJ 12849 - 본대 산책 (0) | 2017.10.07 |
BOJ 5721 - 사탕 줍기 대회 (0) | 2017.09.30 |