1149번 : RGB거리

정말 간단한 dp문제이다.

제시된 조건은

1. 모든 집들은 일직선상에 나란히 있다고 생각.

2. 모든 집에 빨강, 초록, 파랑 중 한가지 색깔로 집을 칠해야함.

3. 이웃한 집에는 같은 색으로 칠할 수 없음.

4. 비용의 최솟값을 구하여라.

dp[i][3]으로 구성한다. ex) i번째를 빨강으로 칠하는 최소 비용 = dp[i][0]

i번째 집을 특정 색상 c1로 칠하려면 i-1번째 집은 색상 c2 또는 c3로 칠해져 있어야 한다.

최솟값을 구하려면 dp[i-1][c2]와 dp[i-1][c3] 중 더 적은 값에 현재 c1의 비용을 더해주면 dp[i][c1]이 완성된다.

같은 방법으로 c2로 칠할때와 c3로 칠해줄 때를 모두 구해주면 된다.

#include <stdio.h>

int dp[1001][3], N;

int MIN(int a, int b) {

return a < b ? a : b;

}

int main() {

scanf("%d", &N);

for (int i = 1; i <= N; ++i) {

int R, G, B;

scanf("%d %d %d", &R, &G, &B);

dp[i][0] = MIN(dp[i - 1][1], dp[i - 1][2]) + R;

dp[i][1] = MIN(dp[i - 1][0], dp[i - 1][2]) + G;

dp[i][2] = MIN(dp[i - 1][0], dp[i - 1][1]) + B;

}

printf("%d", MIN(dp[N][0], MIN(dp[N][1], dp[N][2])));

}