(1149)(DP) 백준 RGB거리

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

풀이

---

 

arr[1][1]    arr[1][2]    arr[1][3]

arr[2][1]    arr[2][1]    arr[2][3]

arr[3][1]    arr[3][2]    arr[3][3]    <<----    와 같은 구조를 가지므로 무조건 같은 단(행)에 있는 숫자중에 최소값만 골라서 내려간다고 결과값이 최소가 나오지 않는다는 것을 쉽게 알 수 있었다. 그래서 각 경우의 값들을 모두 비교해줘야한다. 그러기 때문에 1번째 단부터 2,3,... N번째 단까지 한 단씩 3개의 행렬 모두에 최소의 값을 누적하여 저장하면서 내려가는 알고리즘을 짜면된다. 한 단에 3개의 배열이 존재하는데 이웃끼리는 같은 색깔로 색을 칠할 수 없다. 

이 조건을 유의하면 3가지 경우로 나눌 수 있는데

1. K번째 단의 임의의 배열 / arr[i][j]    arr[i][j+1]    arr[i][j+2] / 에서  arr[i][j]에 윗 단의 최소값을 누적하는경우

---

if(j == 1) arr[i][j] += Min(arr[i-1][j+1], arr[i-1][j+2]);

2. K번째 단의 임의의 배열 / arr[i][j]    arr[i][j+1]    arr[i][j+2] / 에서 arr[i][j+1]에 윗 단의 최소값을 누적하는 경우

---

else if(j == 2) arr[i][j] += Min(arr[i-1][j-1], arr[i-1][j+1]);

3. K번째 단의 임의의 배열 / arr[i][j]    arr[i][j+1]    arr[i][j+2] / 에서 arr[i][j+2]에 윗 단의 최소값을 누적하는 경우

---

else arr[i][j] += Min(arr[i-1][j-2], arr[i-1][j-1]);

위의 세가지 경우로 나누어서 코드를 짜면 된다. 

그리고 가장 마지막 단에서 누적된 3개의 배열의 값을 비교해주고 가장 최소값을 출력해 주기만 하면 된다.

#include <stdio.h>
 
int Min(int a, int b) {
    return a < b ? a : b;
}
 
int main() {
    int N;
    int arr[1001][3] = { 0 };
    
    scanf("%d", &N);
    
    for (int i = 1; i <= N; i++) {
         for (int j = 1; j <= 3; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= 3; j++) {
            if (j == 1) {
                arr[i][j] += Min(arr[i - 1][j + 1], arr[i - 1][j + 2]);
            }
            else if(j == 2) {
                arr[i][j] += Min(arr[i - 1][j - 1], arr[i - 1][j + 1]);
            }
            else {
                arr[i][j] += Min(arr[i - 1][j - 2], arr[i - 1][j - 1]);
            }
        }
    }
 
    printf("%d", Min(Min(arr[N][1], arr[N][2]) , arr[N][3]));
}