백준 17404: RGB거리 2

문제 요약

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

문제 분류

• 다이나믹 프로그래밍

문제 풀이

포스팅하진 않았지만, 백준 1149번: RGB거리문제와 비슷한 문제인데, 조건이 하나가 더 추가되었다. 원래는 양 옆만 신경쓰면 되었지만, 이제는 첫 번째 인덱스와 마지막 인덱스의 경우도 신경써주어야 한다.

따라서 3차원dp배열을 통해 해결했다. 2차원 배열은 각각 인덱스와 해당 인덱스에 칠해지는 색깔이다. 3번째 인자는 처음 시작된 곳의 색깔이다. 가령 똑같은 인덱스에 똑같은 색깔을 칠한다고 하더라도, 시작 인덱스(0번째)의 색깔이 다르다면 다른 값을 가져야 한다. 따라서 첫 인덱스의 색깔에 따라 다시 분류하여야 하므로 3차원 배열을 사용하였다.

탑다운 방식으로 0부터 순회하게 되는데, 만약 마지막 집에 칠해야 하는 색깔이 첫번째 칠한 색깔과 같다면 불가능함을 리턴한다. 그렇지 않고 칠할 수 있다면, 그 비용을 반환한다. 현재 집을 순회하면서 다음 집을 방문하는데, dp에는 현재 집에 칠하는 색과 다른 색을 칠한 경우의 최소를 저장해준다.니라 누적임에 유의한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#define INF 2000000000

using namespace std;

int dp[1000][3][3], cost[1000][1000], n;

int dfs(int idx, int color, int start) {
	if (dp[idx][color][start] != 0) return dp[idx][color][start];
	if (idx == n - 1) {
		if(color == start)
			return INF;
		return cost[idx][color];
	}
	if (color == 0)
		dp[idx][color][start] = min(dfs(idx + 1, 1, start), dfs(idx + 1, 2, start));
	else if (color == 1)
		dp[idx][color][start] = min(dfs(idx + 1, 0, start), dfs(idx + 1, 2, start));
	else if (color == 2)
		dp[idx][color][start] = min(dfs(idx + 1, 0, start), dfs(idx + 1, 1, start));
	dp[idx][color][start] += cost[idx][color];
	return dp[idx][color][start];
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++)
			scanf("%d", &cost[i][j]);
	}
	printf("%d", min(min(dfs(0, 0, 0), dfs(0, 1, 1)), dfs(0, 2, 2)));
	return 0;
}