백준 1149번 RGB거리[C++]

1149번 문제를 처음 보았을 때 간단한 문제라고 생각했는데, 문제를 풀면서 주춤하게 되었습니다.

일반적인 dp문제라면 하나의 값만 수정을 해주었지만, 이번 문제는 3개의 값을 수정해주면서 계속 진행해야 합니다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1000][3] = {0};

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%d %d %d", &dp[i][0], &dp[i][1], &dp[i][2]);
    }
    for(int i = 1; i < n; i++){
        dp[i][0] = min(dp[i][0] + dp[i-1][1], dp[i][0] + dp[i-1][2]);
        dp[i][1] = min(dp[i][1] + dp[i-1][0], dp[i][1] + dp[i-1][2]);
        dp[i][2] = min(dp[i][2] + dp[i-1][0], dp[i][2] + dp[i-1][1]);
    }
    printf("%d", min({dp[n-1][0], dp[n-1][1], dp[n-1][2]}));
    return 0;
}

따라서 dp[][0]에는 빨간색 dp[][1]에는 초록색 dp[][2]에는 파랑색이므로  해당 배열값에 총 최소값을 저장합니다.

구하는 점화식은 해당 페인트 실하는 비용 + 해당페인트색과 다른 색을 선택한 페인트중 min값을 선택하여 저장해줍니다.