17404 RGB거리 2

이 문제에 접근이 어렵다면 쉬운 문제부터 풀어보도록 하자.

www.acmicpc.net/problem/1149

1149번: RGB거리

문제를 자세히 보면, 부분 문제들로 구성된걸 알 수 있다.

0 : R, 1 : G, 2 : B 색깔이라 하면 점화식을 다음과 같이 구성할 수 있다.

dp[N][K] = N번째 집을 K번째 색깔로 칠하는 경우의 최솟값
e.g.) dp[N][1] = min(dp[N - 1][0] + color[N][1], dp[N - 1][2] + color[N][1])

우리가 알고 싶은건 N번째 집을 칠한 모든 경우들의 최솟값이다.

그러나, 주의할 점은 첫 번째 집을 칠한 색깔에 따라 마지막 집을 색칠하는 경우에도 영향을 끼친다.

따라서, 처음 집을 칠할 때의 경우를 상정하고 dp를 돌리고 얻은 결과 값에서 최솟값을 갱신한다.

경우를 상정하는 방식은 지정한 색 외의 비용을 커다란 값으로 초기화하도록 했다.

 

예를 들어 첫 번째 집을 R색으로 칠했다면, 마지막 집을 G, B색으로 칠한 경우의 최솟값을 저장한다!

 

정답코드

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_SIZE 1000
#define INF 987654321
int dp[MAX_SIZE][3];
int color[MAX_SIZE][3];
int N;
void setting()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < 3; j++)
			dp[i][j] = INF;
}
int main()
{
	int result = INF;
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < 3; j++)
			scanf("%d", &color[i][j]);
	setting();
	dp[0][0] = color[0][0];
	dp[0][1] = color[0][1];
	dp[0][2] = color[0][2];
	for (int k = 0; k < 3; k++) {
		for (int j = 0; j < 3; j++) {
			//미리 색을 지정해놓는다.
			if (k == j)
				dp[0][j] = color[0][j];
			else
				dp[0][j] = INF;
		}
		for (int i = 1; i < N; i++) {
			dp[i][0] = min(dp[i - 1][1] + color[i][0], dp[i - 1][2] + color[i][0]);
			dp[i][1] = min(dp[i - 1][0] + color[i][1], dp[i - 1][2] + color[i][1]);
			dp[i][2] = min(dp[i - 1][0] + color[i][2], dp[i - 1][1] + color[i][2]);
		}
		for (int j = 0; j < 3; j++) {
			//첫 번째 집에서 칠한 색과 다른 경우의 최솟값을 갱신한다.
			if (k != j)
				result = min(result, dp[N - 1][j]);
		}
	}
	printf("%d\n", result);
	return 0;
}