백준 1949번 우수 마을

문제 링크입니다: https://www.acmicpc.net/problem/1949

1949번: 우수 마을

트리 자료구조를 활용한 DP 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 나라가 트리 구조로 이루어지고 있기 때문에 우선 트리의 구조를 createTree 함수를 통해 구성합니다.

1.1 트리의 경우 사이클을 이루지 않기 때문에 어느 마을이나 root 로 선정해도 됩니다. 따라서 편리하게 마을 번호의 시작점인 1을 루트로 지정했습니다.

2. func 함수의 경우 매개변수로 현재 마을 번호 와 우수 마을 여부 를 전달 받습니다.

2.1 현재 마을이 우수 마을이라면 다음 마을은 필연적으로 우수 마을이 아닙니다.

2.2 현재 마을이 우수 마을이 아니라면 다음 마을은 우수 마을일수도 우수 마을이 아닐 수도 있습니다.

2.3 2.1과 2.2번의 경우를 모두 따져 우수마을이라면 결과에 주민수를 더해줍니다.

3. 2번의 모든 경우를 따져 최대 우수 마을 주민수들의 합을 구해줍니다.

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~