[BOJ] 백준 1949 우수 마을 (Swift)

문제

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

1949번: 우수 마을

풀이

트리에서 DP를 사용하는 문제입니다.

1. 현재 마을이 우수 마을 이라면 다음 마을은 절대 우수 마을이 될 수 없습니다.
2. 현재 마을이 우수 마을 이라면 다음 마을은 우수 마을일 수도 있고 아닐 수도 있습니다.

여기서 dp로 사용할 배열의 점화식을 다음과 같이 정의할 수 있습니다.
$f(n, 0) =$: n번째 마을이 우수 마을이 아님
$f(n, 1) =$: n번째 마을이 우수 마을임

점화식: $f(n, 0) = max(f(next, 0), f(next, 1))$: n번째 마을이 우수 마을이 아니면, 다음 마을이 우수 마을일 때와, 아닐 때 중 더 큰 값
$f(n, 1) = cost(n) + f(next, 0)$: n번째 마을이 우수 마을이면, 현재 가중치 + 다음 마을이 우수 마을이 아닐 때

소스코드

후기

아직까지 DP 문제들에 익숙하지 않은지.. DP만 보면 너무 어렵다는 생각이듭니다..
DP 문제들은 풀이를 보면 이해하는데, 풀이를 떠올리기가 항상 어려운 것 같습니다.