1149_RGB거리

다이나믹 프로그래밍 방법으로 풀 수 있다. 

i+1은 i와 같은 색깔이 아니면서 최소의 비용을 갖아야 한다. 

구조는 [집의번호][색깔]을 사용한다. => dy[i][j]

식 : i까지의 최소 비용 + 해당색깔로 칠했을 때의 비용

을 기본 식으로 사용하여 코딩해나간다.

다음과 같이 코딩해주었다.

void dp(){ dy[1][1] = arr[1][1]; dy[1][2] = arr[1][2]; dy[1][3] = arr[1][3]; for (int i = 2; i <= n; i++){ for (int j = 1; j <= 3; j++){ for (int k = 1; k <= 3; k++){ if (j == k) continue; if (dy[i - 1][k] + arr[i][j] < dy[i][j]) dy[i][j] = dy[i - 1][k] + arr[i][j]; } } } }