RGB거리 2 (feat. 백준, 17404번)

RGB거리 2
https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, ans = static_cast<int>(1e8), arr[1000][3], dp[1000][3];
	cin >> N;
	for (register int n = 0; n < N; ++n)
		for (register int i = 0; i < 3; ++i)
			cin >> arr[n][i];
	for (register int i = 0; i < 3; ++i) {
		for (register int j = 0; j < 3; ++j)
			if (i == j)		dp[0][j] = arr[0][j];
			else			dp[0][j] = static_cast<int>(1e8);
		for (register int j = 1; j < N; ++j) {
			dp[j][0] = min(dp[j - 1][1], dp[j - 1][2]) + arr[j][0];
			dp[j][1] = min(dp[j - 1][0], dp[j - 1][2]) + arr[j][1];
			dp[j][2] = min(dp[j - 1][0], dp[j - 1][1]) + arr[j][2];
		}
		for (register int j = 0; j < 3; ++j) {
			if (i != j)
				ans = min(dp[N - 1][j], ans);
		}
	}
	cout << ans;
	return 0;
}
// *&)*@*

1. N이 3이라고 했을때, 1번집과 2번집 / 2번집과 3번집 이 서로 다른 경우는 다음과 같습니다.
   - 1번은 빨강 2번은 노랑 3번은 파랑
   - 1번은 빨강 2번은 노랑 3번은 빨강
   - 1번은 빨강 2번은 파랑 3번은 노랑
   - 1번은 빨강 2번은 파랑 3번은 빨강
   - 1번은 노랑 2번은 빨강 3번은 파랑
   - 1번은 노랑 2번은 빨강 3번은 노랑
   - 1번은 노랑 2번은 파랑 3번은 빨강
   - 1번은 노랑 2번은 파랑 3번은 노랑
   - 1번은 파랑 2번은 빨강 3번은 노랑
   - 1번은 파랑 2번은 빨강 3번은 파랑
   - 1번은 파랑 2번은 노랑 3번은 빨강
   - 1번은 파랑 2번은 노랑 3번은 파랑
   
   
2. 하지만 1번과 3번은 같은 색을 가질 수 없으므로 위의 삭제선에 해당되는 경우는 빼주어야 합니다.
3. 이를 dp로 옮겼을때 코드와 같게 됩니다.