문제

문제 링크

해설

• 인접한 두 집의 색상이 같아서는 안 된다는 규칙이 중요합니다.
• 하나의 집을 세 가지 색깔로 칠할 수 있기 때문에 i번째 집에 3가지 경우의 수가 생깁니다.
• 그러므로, DP[i][0] = i번째 집을 빨간색으로 칠했을 때 최소 비용으로 정의합니다.
• 인접한 두 집의 색은 같을 수 없기 때문에,
  • i번째 집이 R인 경우, i - 1번째 집은 G, B만 올 수 있습니다.
  • i번째 집이 G인 경우, i - 1번째 집은 R, B만 올 수 있습니다.
  • i번째 집이 B인 경우, i - 1번째 집은 R, G만 올 수 있습니다.
• 위 세 문장을 그대로 코드로 작성하면 아래와 같습니다.

DP[i][0] = DP[i - 1][1] + DP[i - 1][2];
DP[i][1] = DP[i - 1][0] + DP[i - 1][2];
DP[i][2] = DP[i - 1][0] + DP[i - 1][1];

• N번째 집까지 모두 칠했을 때의 최소 경비는 [0], [1], [2] 중 최솟값입니다.
• 따라서 정답은 min(min([0], [1]), [2]);로 출력하면 됩니다.

코드

#include <iostream>
using namespace std;

int N, A[1001][3], DP[1001][3];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> A[i][0] >> A[i][1] >> A[i][2];
	
	DP[1][0] = A[1][0]; DP[1][1] = A[1][1]; DP[1][2] = A[1][2];
	for (int i = 2; i <= N; ++i) {
		DP[i][0] = min(DP[i - 1][1], DP[i - 1][2]) + A[i][0];
		DP[i][1] = min(DP[i - 1][0], DP[i - 1][2]) + A[i][1];
		DP[i][2] = min(DP[i - 1][0], DP[i - 1][1]) + A[i][2];
	}
	cout << min(min(DP[N][0], DP[N][1]), DP[N][2]);
}

소스코드 링크

결과