[c++] 백준 17404 RGB거리 2

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

17404번: RGB거리 2

1149번 RGB거리(https://www.acmicpc.net/problem/1149)와 풀이는 같지만, 1번 집과  N번 집의 색이 다른 경우를 모두 해본다.

그 경우들은

빨강, 파랑

빨강, 초록

초록, 빨강

초록, 파랑

파랑, 빨강

파랑, 초록

와 같다.

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000*1000+1
int arr[1010][3];
int dp[1010][3];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin>>n;
    int ans = MAX;
    for(int i=0; i<n; i++)
        for(int j=0; j<3; j++)
            cin>>arr[i][j];
    for(int k=0; k<3; k++){ // 1번 집의 색을 k로 고정
        for(int j=0; j<3; j++){ // dp배열 초기값
            if(k == j)
                dp[0][j] = arr[0][j];
            else
                dp[0][j] = MAX;
        }
        //dp 점화식 돌리기
        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];
        }
        for(int t=0; t<3; t++){ // N번 집 색 t로 정하기
            if(t == k) // 1번 집과 N번 집 색이 같으면 스킵
                continue;
            ans = min(ans, dp[n-1][t]);
        }
    }
    cout << ans;
    return 0;
}