[BOJ] 1149번. RGB거리

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

문제는 링크 참고.

풀이.

dy[i][j] : i번째집이 j번째 색으로 칠했을 때 들 수 있는 가장 적은 비용

dy[i][j] = dy[i][j] + MIN(dy[i][(j + 1) % 3], dy[i][(j + 2) % 3]);

여기서 R은 0, G는 1, B는 2로 했다.

입력 예제 설명.

입력예제 : 

3
26 40 83
49 60 57
13 89 99

0번째 집이 색칠 하는 경우

R : 26

G : 40

B : 83

1번째 집이 색칠 하는 경우

R : 49 + MIN(0번째 집 G를 칠 했을 때 비용, 0번째 집 B를 칠 했을 때 비용)

G : 60 + MIN(0번째 집 R를 칠 했을 때 비용, 0번째 집 B를 칠 했을 때 비용)

B : 57 + MIN(0번째 집 R를 칠 했을 때 비용, 0번째 집 G를 칠 했을 때 비용)

2번째 집이 색칠 하는 경우

R : 13 + MIN(1번째 집 G를 칠 했을 때 비용, 1번째 집 B를 칠 했을 때 비용)

G : 89 + MIN(1번째 집 R를 칠 했을 때 비용, 1번째 집 B를 칠 했을 때 비용)

B : 99 + MIN(1번째 집 R를 칠 했을 때 비용, 1번째 집 G를 칠 했을 때 비용)

마지막 집에서의 값 중 MIN 값을 구하면 색칠할 때 최소로 드는 비용을 구할 수 있다.

#include <stdio.h>
#include <stdlib.h>
 
#define MIN(x,y) (x < y ? x : y)
#define MAX_N 1001
 
int main() {
    int N = 0;
    int dy[MAX_N][3] = {0};
    
    scanf("%d", &N);
    
    for (int i = 0 ; i < N ; i ++) {
        for (int j = 0 ; j < 3 ; j ++)
            scanf("%d", &dy[i][j]);        
    }
    
    for (int i = 1 ; i < N ; i ++) {
        for (int j = 0 ; j < 3 ; j ++)
            dy[i][j] += MIN(dy[i - 1][(j + 1) % 3], dy[i - 1][(j + 2) % 3]);
    }
    
    printf("%d", MIN(dy[N - 1][0], MIN(dy[N - 1][1], dy[N - 1][2])));
    
    return 0;
}