✅ DP

문제

링크

1. 문제 접근 및 해결 로직

1. 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
2. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
3. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

조건이 3가지나 되지만 잘 생각해보면 결국 양쪽으로 인접한 집들은 같은 색으로 칠 할 수 없다는 말이다.

따라서 n번째 집이 칠해질 수 있는 색깔은 이전 n-1번째 집이 무슨 색이었느냐에 따라 결정된다.

• 칠하는 비용은 최소가 되어야 하므로 이전 집의 경우중에 칠하는 비용이 더 적은 색상을 선택한다.
• 각 집에 칠할 수 있는 있는 색상은 RGB 3가지이므로 각각의 경우를 따로 세어줘야 한다.

• 정의
  $f(i,c)$ : $i$ 집까지 칠하는 비용의 최솟값, $i$ 집의 색상은 $c(R/G/B)$
• 구하는 답
  $min(f(N,R),f(N,G),f(N,B))$
• 초기값
  $f(1,R)=price(G)$
  $f(1,G)=price(G)$
  $f(1,B)=price(G)$
• 점화식
  $f(i,R)=min(f(i-1,G),f(i-1,B))+price(R)$
  $f(i,G)=min(f(i-1,R),f(i-1,B))+price(G)$
  $f(i,B)=min(f(i-1,R),f(i-1,G))+price(B)$

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항