17404번 RGB거리 2

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

17404번: RGB거리 2

 

RGB거리 1과 유사한 문제지만 

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

밑줄 친 부분의 조건이 추가되었다. 따라서 DP의 초깃값을 정할 수 없으므로 1번 집을 빨간색으로 고정, 초록색으로 고정, 파란색으로 고정하는 경우를 다 계산해주고 마지막 집은 1번 집과 같은 색이 될 수 없으므로 계산하지 않는다.

#include <bits/stdc++.h>
#define l long long
#define INF 2e9
#define p pair<int,int>
#define vc vector<int>
#define F first
#define S second
using namespace std;

int dp[1001][4],RGB[1001][4];

int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int n,ans = INF;
    cin >> n;

    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++)
            cin >> RGB[i][j];
    }

    for(int k=0;k<=2;k++){

        for(int i=0;i<=2;i++){
            if(i == k) dp[1][i] = RGB[1][i];
            else dp[1][i] = 1000 * 1000 + 1;
        }

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

        for(int i=0;i<=2;i++){
            if(i == k) continue;
            ans = min(ans,dp[n][i]);
        }
    }

    cout << ans;
}