BOJ 17404 - RGB 거리 2

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

 

접근

기존 RGB 거리 문제에서 첫 번째 집과 마지막 집의 색을 고려하는 조건이 추가된 문제이다.

DP를 이용하여 풀게되면 마지막 집을 칠할 때, 첫번째로 어떤 집을 선택했는지 알 수 없다.

따라서, 첫 번째 집을 칠할 색을 저장하고 마지막 집의 색을 고려해야 한다.

 

첫 번째 집을 고르는 경우를 for문을 통해 선택하고, 기존 처럼 진행하면 된다.

그러나 여기서 문제되는 부분이 있다.

 

첫 번째 집을 Red를 선택한다고 가정해보자.

dp[1][1] = arr[1][1];

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

 위 코드에서 dp[i][1] = min(dp[i - 1][2], dp[i - 1][3]) + cost[i][1];을 하는 순간 dp[1][1] 대신 dp[1][2] 나 dp[1][3]이 선택될 수 있다. 따라서 이를 방지하기 위해 첫번째 집에 선택된 색 외에는 MAX를 넣어 선택되는 일을 방지하자.

 

for (int rgb = 1; rgb <= 3; rgb++) {

    for (int i = 1; i <= 3;i++) {
        if (i == rgb) {
            dp[1][i] = cost[1][rgb];
        }
        else {
            // 선택 되지 않은 색은 선택되지 않게 최대치로 고정
            dp[1][i] = MAX;
        }
    }

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

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX 9999999

int n;
int cnt;
int res = MAX;
int cost[1001][4];
int dp[1001][1001];

int main() {

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

	for (int rgb = 1; rgb <= 3; rgb++) {

		for (int i = 1; i <= 3;i++) {
			if (i == rgb) {
				dp[1][i] = cost[1][rgb];
			}
			else {
				dp[1][i] = MAX;
			}
		}
		
		for (int i = 2; i <= n; i++) {
			dp[i][1] = min(dp[i - 1][2], dp[i - 1][3]) + cost[i][1];
			dp[i][2] = min(dp[i - 1][1], dp[i - 1][3]) + cost[i][2];
			dp[i][3] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][3];
		}

		for (int i = 1; i <= 3; i++) {
			if (i == rgb) {
				continue;
			}

			res = min({ res, dp[n][i] });
		}
		
	}

	cout << res;
}