1949 (1) 썸네일형 리스트형 [BOJ] 백준 1949 우수 마을 (Swift) 문제 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 풀이 트리에서 DP를 사용하는 문제입니다. 현재 마을이 우수 마을 이라면 다음 마을은 절대 우수 마을이 될 수 없습니다. 현재 마을이 우수 마을 이라면 다음 마을은 우수 마을일 수도 있고 아닐 수도 있습니다. 여기서 dp로 사용할 배열의 점화식을 다음과 같이 정의할 수 있습니다. $f(n, 0) =$: n번째 마을이 우수 마을이 아님 $f(n, 1) =$: n번째 마을이 우수 마을임.. 이전 1 다음
