1149번: RGB거리

https://www.acmicpc.net/problem/1149

1149번: RGB거리

i번 집의 색이 i - 1번 집의 색과 달라야 하므로 i번 집을 k번째 색으로 색칠할 때까지 사용되는 비용의 합은

i - 1번 집을 k가 아닌 색으로 색칠할 때까지 사용되는 비용의 합 + i번 집을 k번째 색으로 색칠하는 비용이다.

#include <cstdio>

#define MAX_N 1000

// col[i][j] : i번째 집을 j번째 색으로 칠할 때 드는 비용
int col[MAX_N + 1][3] = {{ 0, }};

int min(int a, int b) { return a < b ? a : b; }

int main() {
    // 집의 개수
    int N;
    scanf("%d", &N);

    // i번 집을 색칠할 때
    for (int i = 1; i <= N; i++) {
        scanf("%d %d %d", &col[i][0], &col[i][1], &col[i][2]);

        // 이전 집을 현재 집과 다른 색으로 칠할 때까지의 총 비용을
        // 현재 집을 현재 색으로 칠하는 비용에 더한다
        col[i][0] += min(col[i - 1][1], col[i - 1][2]);
        col[i][1] += min(col[i - 1][0], col[i - 1][2]);
        col[i][2] += min(col[i - 1][0], col[i - 1][1]);
    }

    // col[N]에는 모든 집의 최소 비용이 저장되어 있으므로
    // 이 세 최소비용 중 최솟값을 출력한다
    printf("%d\n", min(col[N][0], min(col[N][1], col[N][2])));

    return 0;
}