[백준 17404] RGB거리 2

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

17404번: RGB거리 2

RGB거리 1과 달라진 점은

 

집들이 서로 원형으로 이어져 있어서

 

점화식이 시작하는 초기 조건을 잡을 수 없다는 것이다.

 

---

 

확실한 것은 첫 번째 집이 적어도 RGB 세 가지 색 중 하나로 칠해져 있다는 것이다.

 

각각의 색을 한번에 처리하는 것이 아니라

 

따로따로 구한다면 생각보다 쉽게 처리할 수 있다.

 

1. 첫번째 집을 R로 칠한다고 가정했을 때 최소 비용

 

2. 첫번째 집을 G로 칠한다고 가정했을 때 최소 비용

 

3. 첫번째 집을 B로 칠한다고 가정했을 때 최소 비용

 

위 세가지 비용 중에 최소가 정답이다.

 

---

 

물론 첫번째 집이 G일 때 구하는 최소 비용에서 R과 B만 고려하고 마지막 집이 G로 칠해질 때는 배제해야 된다.

 

첫 번째 집이 R과 B로 칠해져 있을 때도 마찬가지이다.

 

---

코드에서 첫 번째 집을 특정 색으로 칠했을 때

 

나머지 색은 가능한 정답보다 더 큰 수를 적음으로써 무시하게 하였다.

 

여기서는 1000005

 

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

int main(void) {
	int n;
	int house[3][1005];
	int dp[3][1005];

	cin >> n;

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

	int res = 1000005;

	for (int k = 0; k < 3; k++) {
		dp[0][0] = 1000005;
		dp[1][0] = 1000005;
		dp[2][0] = 1000005;
		dp[k][0] = house[k][0];

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

		for (int i = 0; i < 3; i++) {
			if (i == k)continue;
			res = min(res, dp[i][n - 1]);
		}
	}

	cout << res << endl;

	return 0;
}