트리-DP. [1949]

[1. 문제 설명]

https://www.acmicpc.net/problem/1949

---

[2. 풀이 접근]

처음에는 완전 탐색 형식으로 풀어보고,

메모이제이션 해서 최적화 하는 방법으로 접근해보려 했는데,

이 때, 문제에서 조건 중 3번 조건을 다루기가 많이 까다로웠다.

• root 가 선택되지 않았을 때, 적어도 하나의 자식은 우수 마을로 선정되어야 한다.
• 자식 노드의 개수가 4 개일 때, 전체 경우의 수는 (2^4-1) 개 이다.
  # 전체 경우의 수에서, 모두 우수 마을이 아닌 경우를 뺀 개수
• 자식 노드의 개수가 늘어나면 지수 형태로 경우의 수가 늘어나므로, 적절한 풀이가 아니다.

찾아보니 일반적인 풀이는 아래와 같다.

• 부분 문제를 다음과 같이 정의
  # 어떤 노드를 root 로 하는 서브 트리에서 최대 주민 수를 반환.
• 그래서 전체 트리의 root 에서 시작하여, dfs 탐색
• 이 때, 반복적 동적계획법으로 최대 값을 갱신해 나간다.

이 때, 좀 더 생각해봐야 될 것이 한가지 존재했는데,

이번 root 에 대한 부분 문제를 풀 때,

이번 root가 우수 마을로 선정되지 않았을 때, 어떤 자식을 선택해야 하는 가이다.

• 위에서 고민했던 것과 같은 상황이다.

아래 그림과 같은 상황이다.

이번 루트를 선택하지 않았는데,  자식 노드를 선택하는 것이 전체 주민 수를 최대로 할 수 없는 것이라면,

과연 어떻게 하는게 좋을 까를 꽤 오래 고민하였는데,

답은 간단했다.

이런 상황에서는 root 의 자식을 우수 마을로 선정하지 않고, root 를 우수마을로 선정하면 되는 것이다.

부분 문제를 푸는 것이기 때문에 root 의 부모가 어떤 상태인지는 굳이 알 필요가 없다.

• 부분 문제라는 것이 가장 크다.
• 이번 root 의 부모의 상태를 고려할 필요가 없다.
• 이번 부분 문제에 대한 결과를 이용해서, 원래 부모가 문제를 해결해야 한다.

---

[3. 코드]