BOJ 1949 - 우수 마을

문제 링크(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)

---

 - 

※ 정확하고 부드러운 태클은 언제나 환영입니다.