[백준/BOJ] 백준 1949번 : 우수 마을

www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 트리DP(트리에서 다이나믹 프로그래밍)을 통해 문제를 해결했으며 cache[노드 번호][우수마을인지 아닌지][이전마을이 우수마을인지 아닌지]를 통해 문제를 해결했다. 유의할 점은 here이 우수마을이 아닌데, 이전 마을도 우수마을이 아니었을 경우이다 이때 there한곳은 무조건 우수마을이어야 하는데 자동적으로 there이 우수마을인 경우가 최적이 되는 경우에는 상관없지만 그렇지 않다면 우수마을로 선택했..

2021.02.28