1149번 RGB거리

문제링크 : https://www.acmicpc.net/problem/1149

해결방법 :

RGB 거리의 모든 집들을 R,G,B 색으로 칠했을때 드는 최소비용을 구하는 문제인데, 나는 제일 마지막집을 때내어 생각했다. 

제일 마지막 집이 빨간색으로 칠해질 때 이웃한 집은 G, B 두가지중 하나로만 색칠해야된다.

마찬가지로 그린 이라면 이웃한 집은 R,B 두가지 중 하나로 칠해져야한다.

즉, 하나의 색깔이 정해지면 이웃한집은 그에 따라 두가지의 경우로 나눠진다.

위의 컨셉을 이용해서 점화식을 세워보면 다음과 같이 만들 수 있다.

D[N][0] = N번째 집이 빨간색으로 칠할 때,  모든 집의 최소비용 으로 정의한다. (0 : 레드, 1 : 그린, 2: 블루)

그러면 D[N][0] = min(D[N-1][1], D[N-1][2]) + rgb[N][0]  의 점화식을 세울 수 있다.

마지막집이 r,g,b 세가지의 경우를 가지기 때문에 D[N][0], D[N][1], D[N][2] 를 각각 구해서 최소값을 찾으면 답을 구할 수 있다.

소스코드)

#include<stdio.h>
int rgb[1001][3];
int Min = 987654321;
int d[1001][3];
int min(int x, int y){return x<y ? x : y;}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i<=n; i++)
    {
        for(int j = 0; j<3; j++)
        scanf("%d", &rgb[i][j]);
    }
    d[1][0] = rgb[1][0];
    d[1][1] = rgb[1][1];
    d[1][2] = rgb[1][2];
    for(int i= 2; i<=n; i++)
    {
        d[i][0] = min(d[i-1][1],d[i-1][2]) + rgb[i][0];
        d[i][1] = min(d[i-1][0],d[i-1][2]) + rgb[i][1];
        d[i][2] = min(d[i-1][0],d[i-1][1]) + rgb[i][2];
    }
    for(int i = 0; i<3; i++)
    {
        if(d[n][i] < Min)
        {
            Min = d[n][i];
        }
    }
    printf("%d",Min);
}