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

BOJ 바로가기

#include <iostream>
using namespace std;
int a[1001][3], d[1001][3];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> a[i][j];
		}
	}
	int mini=1000*1000+1;
	for (int k = 0; k <= 2; k++) { // 첫번째 집의 색깔
		for (int j = 0; j <= 2; j++) { // 첫번째 집
			if (k == j) {
				d[1][j] = a[1][j];
			}
			else {
				d[1][j] = 1000 * 1000 + 1;
			}
		}
		for (int i = 2; i <= n; i++) { // 두번째~마지막 집
			d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0];
			d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
			d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];
		}
		for (int j = 0; j <= 2; j++) { // 첫번째 집의 색깔과 마지막 집의 색깔이 다른 경우 중 최솟값
			if (k == j)
				continue;
			mini = min(mini, d[n][j]);
		}
	}
	cout << mini;
	return 0;
}

RGB 거리보다 조건이 한 개 더 추가되었다. 바로 첫번째 집과 마지막 집의 색이 같으면 안 된다는 것.

📌아이디어

반복문을 이용해 첫번째 집의 색깔을 정해주고 시작한다.

그리고 세 개의 점화식을 통해 d[n][0], d[n][1], d[n][2]를 구해준다. n번째 집이 빨간색일 경우의 최솟값(d[n][0])은 n-1번째 집이 초록색일 경우(d[n-1][1])와 파란색일 경우(d[n-1][2]) 중 최솟값에 a[n][0]을 더해준 값과 같다. n번째 집이 파란색일 경우와 빨간색일 경우에도 마찬가지다.

마지막에는 첫번째 집과 마지막 집의 색깔이 다른 두 가지 경우 중에서 최솟값을 구해주면 답을 도출해낼 수 있다.