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

문제링크 : https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, result = MAX;
int arr[1001][3];
int dp[1001][3];

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

    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    }

    for(int i=0; i<3; i++) //시작 위치
    {
        for(int j=0; j<3; j++) //1번 집
        {
            if(j==i) dp[0][j] = arr[0][j]; //첫 줄 색깔 저장
            else dp[0][j] = 1001; //이외는 선택 불가하도록 가장 큰 값으로 설정
        }

        for(int j=1; j<N; j++) //i번째 집
        {
            dp[j][0] = arr[j][0] + min(dp[j-1][1], dp[j-1][2]); //현재값 + 그전 값중 작은 값
            dp[j][1] = arr[j][1] + min(dp[j-1][0], dp[j-1][2]);
            dp[j][2] = arr[j][2] + min(dp[j-1][0], dp[j-1][1]);
        }

        for(int j=0; j<3; j++) //N번째 집
        {
            if(j==i) continue; //1번 집과 같으면 넘김
            result = min(result, dp[N-1][j]);
        }
    }
    cout << result;
    return 0;
}

백준 1149번 문제인 RGB 거리 문제에서 업그레이된 문제이다.

맨 처음 첫 줄에 시작 위치를 정하고 시작한다.

3개 중에 하나를 정하고, 나머지 2개는 1001로 설정함으로써 이후 DP를 통해 탐색할때 선택되는 일이 없도록 한다.

 

i번째의 값은 현재 칸을 기준으로 그전 값 2개중에 작은 값을 선택하도록 해준다.

이를 N번째 값까지 쭉 계산을 진행해준다.

현재 칸 0 -> 선택 가능한 이전 칸 1, 2
현재 칸 1 -> 선택 가능한 이전 칸 0, 2
현재 칸 2 -> 선택 가능한 이전 칸 0, 1

 

N번째 집의 경우에는 1번째 집과 같으면 안된다는 조건이 있다.

따라서 마지막 3개의 칸에 대해 반복문을 돌리면서 1번째 집의 칸과 똑같은 경우에는 넘기고,

아닐 때에는 가장 작은 값을 result에 저장하도록 해준다.