(C++) - 백준(BOJ)코딩 1149번 : RGB거리

www.acmicpc.net/problem/1149

1149번: RGB거리

2차원 bottom up dp로 풀었습니다.

 

 

풀이방법

 

D[i][j] = i번째 집을 j색으로 칠할 때 최소 비용 빨강:1 초록:2 파랑:3  D[1][1] = A[1][1]; D[1][2] = A[1][2]; D[1][3] = A[1][3];

A[i][j] = 입력

j로 칠했을 때 i-1, i+1번째 집은 j색으로 칠할 수 없다.

  1.i번째 집을 R로 칠했을 때 (2 <= i <= N)(1 <= j <= 3) D[i][j] = min(D[i-1][2],D[i-1][3])+A[i][j]

  2.           G로 칠했을 때 (2 <= i <= N)(1 <= j <= 3) D[i][j] = min(D[i-1][1],D[i-1][3])+A[i][j]

  3.           B로 칠했을 때 (2 <= i <= N)(1 <= j <= 3) D[i][j] = min(D[i-1][1],D[i-1][2])+A[i][j]

D[i][j] = min(D[i-1][j가 아닌],D[i-1][j가 아닌 또 다른])+A[i][j]

 

Code

#include <iostream>
#include <algorithm>
using namespace std;
int D[1001][4],A[1001][4],N;
int main() {
    cin >> N;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= 3; j++)
            cin >> A[i][j];
    D[1][1] = A[1][1];
    D[1][2] = A[1][2];
    D[1][3] = A[1][3];
    for (int i = 2; i <= N; i++)
        for (int j = 1; j <= 3; j++)
        {

            D[i][1] = min(D[i - 1][2], D[i - 1][3]) + A[i][1];
            D[i][2] = min(D[i - 1][1], D[i - 1][3]) + A[i][2];
            D[i][3] = min(D[i - 1][1], D[i - 1][2]) + A[i][3];
        }
    cout << min(D[N][1], min(D[N][2], D[N][3]));
}