[cpp 알고리즘] 백준 1149 RGB거리 c++

1. 문제

 

2. 풀이

3. 코드

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int arr[1001][3];
int dp[1001][3];

int main(){
    
    // input
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<3; j++){
            cin >> arr[i][j];
        }
    }
    
    // init
    dp[0][0] = arr[0][0];
    dp[0][1] = arr[0][1];
    dp[0][2] = arr[0][2];
    
    // dp[x][0] = arr[x][0] + min(dp[x-1][1], dp[x-1][2])
    for(int i=1; i<N; i++){
        dp[i][0] = arr[i][0] + min(dp[i-1][1], dp[i-1][2]);
        dp[i][1] = arr[i][1] + min(dp[i-1][0], dp[i-1][2]);
        dp[i][2] = arr[i][2] + min(dp[i-1][1], dp[i-1][0]);
    }
    
    int ans = 987654321;
    
    for(int i=0; i<3; i++){
        if(dp[N-1][i] < ans) ans = dp[N-1][i];
    }
    cout << ans;
    return 0;
}

 

4. 리뷰

 dp의 한 행 혹은 열의 값을 고정하고, 나머지를 증가시키면서 값을 계속 비교해 나갈 수 있다. 최소 값이 무엇인지를 찾고 다음으로 넘어가는 게 아니라, 일단은 모든 경우를 구한 후, 다음에 어떤 값이 최소였는지를 선택하게 하니까 문제 해결이 쉬워졌다. 

 

5. 다른 풀이방법