[백준/C,C++] 1149번: RGB거리

www.acmicpc.net/problem/1149

1149번: RGB거리

DP 문제의 경우 점화식을 찾는 과정이 상당히 중요한데 이번 문제에서 점화식을 찾는데 꽤 애먹었습니다. 결국 다른 분들의 해답을 참고한 후 다시 제 식대로 코딩하게 되었습니다.

	1번집	2번집	3번집
빨강색 비용	26	49	13
초록색 비용	40	60	89
파랑색 비용	83	57	99
빨강색 최소 비용	26	min(40, 83) + 49 = 89	min(86, 83) + 13 = 96
초록색 최소 비용	40	min(26, 83) + 60 = 86	min(89, 83) + 89 = 172
파랑색 최소 비용	83	min(26, 40) + 57 = 83	min(89, 86) + 99 = 185

최소 비용 = min(96, 172, 185) = 96 즉, n번째 집을 R, G, B 색상으로 칠하는데 필요한 최소 비용은 칠하려는 색상을 제외한 n - 1번째 집의 색칠 비용 중 더 작은 값에 현재 비용을 더한 것입니다.

#include<iostream>

using namespace std;

#define MAX 1001

int N;
int price[MAX][4];
int DP[MAX][4];

int RGB(void)
{
    for (int i = 1; i <= 3; i++) {
        DP[1][i] = price[1][i];
    }
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= 3; j++) {
            DP[i][j] = price[i][j] + min(DP[i - 1][j % 3 + 1], DP[i - 1][(j + 1) % 3 + 1]);
        }
    }
    return min(DP[N][1], min(DP[N][2], DP[N][3]));
}

int main(void)
{
    cin >> N;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 3; j++) {
            cin >> price[i][j];
        }
    }

    cout << RGB() << endl;

    return 0;
}