[백준/C++] 17404번 RGB거리2

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

17404번: RGB거리 2

우선 이 문제는 RGB거리1의 확장판이다.

직전에 고른 색만 고를 수 없는 것이 아니라, 1번째 집과 N번째 집의 색도 달라야 하므로

원형문제라고 볼 수 있다!

​

1. 우선, RGB색으로 칠하는 비용을 2차원 배열에 모조리 저장한다.
2. for문을 3번 돌려서 1번 집이 R, G, B 색을 차례로 하나씩 선택하는 경우의 최솟값을 계산한다.
3. 1번 집이 만약 Red를 골랐다면, Green과 Blue를 나올 수 없는 큰 값으로 설정하여 선택하지 않도록 해준다.
4. 그리고 점화식을 통해 최솟값을 계산한다. (점화식의 원리는, 현재 비용 + 직전에 고르지 않은 색들 중 최소비용 이다.)
5. 1번 집이 Red를 골랐을 때의 k값은 0이므로, dp[n][0] (= 마지막 N번째 집이 Red를 고르는 경우) 를 제외하고 나머지 값들 중 최솟값을 선택한다!

​

※ 점화식만 잘 도출한다면, 크게 어렵지 않은 문제이다!

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

int n,ans=987654321;
int dp[1001][3];
int cost[1001][3];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[0][2] = 0;

    for (int i = 1; i <= n; i++) {
        cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
    }
    // 1번집의 색을 하나씩 고정하면서 dp
    for(int k=0; k <= 2; k++){
        // 하나를 선택하고 나머지값은 엄청 큰 값을 줘서 선택 안하도록함
        for(int i=0; i <= 2; i++){
            if(i == k) dp[1][k]=cost[1][k];
            else dp[1][i]= 987654321;
        }
        // dp점화식
        for(int i=2;i<=n;i++){
            dp[i][0] = min(dp[i-1][1],dp[i-1][2])+cost[i][0];
            dp[i][1] = min(dp[i-1][0],dp[i-1][2])+cost[i][1];
            dp[i][2] = min(dp[i-1][1],dp[i-1][0])+cost[i][2];
        }
        // 1번집과 N번집 중복 방지
        for(int i=0; i <= 2; i++){
            // 만약 k=0이라면, 빨간색을 선택한 것인데
            // i = k라면, 마지막 N번째 집도 빨간색을 선택한 것이므로
            // 조건에 어긋난다
            if(i == k) continue;
            ans = min(ans, dp[n][i]);
        }
    }

    cout << ans;
    return 0;
}