[B]BOJ1149 , dp 뿌수기

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

모든 집을 칠했을 때의 비용의 최솟값.

1. 모든 경우의 수를 나열한 뒤 정렬하여 최솟값을 찾는 방법

2. 특정 지점으로 돌아가
   이전까지 계산된 값을 활용하여
   중간 지점부터 계산하는 방법

이 있고 후자가 DP이다.

Greedy 알고리즘으로 최적해를 구할 수 없는 이유는

아래와 같은 조건이 있기 때문에

당장 작은 색칠 비용을 선택한다고 해서

최종적으로 가장 적은 색칠 비용이 나오지는 않기 때문이다.

- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.

- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

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

-> 이웃하는 집과 색이 같아서는 안된다.

색칠 비용 배열을 cost = []라고하고 

이 배열 안에 (r , g, b)의 튜플 형태로 색칠 비용이 있다.

처음에는 dp[i]의 1차원 배열로 접근했는데

cost 중 하나를 선택해야하기 때문에 1차원 배열로는 재귀 조건을 만족시킬 수 없었다.

때문에 2차원 배열 관계식을 사용해야한다.

칠할 수 있는 경우의 수는 r, g , b 의 3가지 이므로.

dp[i][0] = min(dp[i-1][1], dp[i-2][2])+ rgb[n][0] 

dp[i][1] = min(dp[i-1][0], dp[i-2][2])+ rgb[n][1]

dp[i][2] = min(dp[i-1][2], dp[i-2][0])+ rgb[n][2]

가능한 이전 dp값중 최솟값  + 해당 집의 칠할 색깔( red, green, blue)