백준 1149 - RGB 거리

1) 점화식
이 문제는 아쉽게도 1차원 dp테이블로는 풀리지 않습니다.
그 이유는 우리가 현재 x번째 집의 색상을 R G B중 어떤것을 선택하는지에 따라
최종적인 결과가 변하기 때문입니다. 즉 2차원 배열로써 R G B 인자를 담는
DP TABLE! int dp[3][101010] 이 필요합니다.

0을 RED, 1을 GREEN, 2를 BLUE로 정의하겠습니다.
dp[0][0] = arr[0][0];
dp[1][0] = arr[0][1];
dp[2][0] = arr[0][2]; 가 초기값이 되겠습니다.
그냥 R G B경우에 따라 주어진 배열의 비용을 넣은것입니다.

그리고 1부터 n - 1까지 반복을 돌려줍니다.
dp[0][x] = min(dp[1][x - 1], dp[2][x - 1]) + arr[x][0];
dp[1][x] = min(dp[0][x - 1], dp[2][x - 1]) + arr[x][1];
dp[2][x] = min(dp[0][x - 1], dp[1][x - 1]) + arr[x][2];
로써 DP 점화식을 정의할수 있겠습니다.
현재 색상과 다른 두가지의 색상중 최솟값을 골라 현재 상태로 지정하는 방식의 점화식입니다. 그리고 x번째 집을 채우는 비용(arr)를 넣는것이죠.

2. source code

#define ll long long
#define pii pair<int, int>
#define mod 10000007
#define INF 100000000
#define pb push_back
#define pi 3.141592
using namespace std;

int arr[1010][3];
int dp[1010][3];

int main(void){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++){
            cin >> arr[i][j];
        }
    }
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    arr[0][0] = arr[0][1] = arr[0][2] = 0;

    for(int i = 1; i <= n; i++){
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) +arr[i][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) +arr[i][1];
        dp[i][2] = min(dp[i - 1][0], dp[i  - 1][1]) +arr[i][2];
    }

    int ans = min(min(dp[n][0], dp[n][1]), dp[n][2]);
    cout << ans << "\n";



    return 0;
}

2차원 DP중에는 쉬운편에 속하는 문제입니다.