(C++) [백준 1149번] RGB거리

https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

문제

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

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

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

[문제 설명]

 

N개의 집을 R,G,B 3가지의 색으로 칠하면서, 3가지 조건을 만족하면 된다.

이때 조건은 잘 읽어보면 결국 i(2<=i<N)번째 집과 i-1번째 집의 색만 다르면 된다. 처음에는 i-1,i,i+1이 서로 달라야 하는줄 알고 좀 고생했다.

그리고 그리디로 풀리지 않는다. 아래 입/출력이 예가 될 수 있다.

예제 입력 5

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

예제 출력 5

253

그리디로 푼다고 생각하면 39-55-37-89-11-13-29-60 순서로 따라가게 되는데, 이 값들의 합은 292이다.

[풀이]

 

처음 생각했던 방법은 그리디였고, 그리디가 아니면 DP라고 생각해서 DP로 풀기 시작했다.

내가 생각한 방법은 다음과 같다.

Color가 R = 0, G = 1, B = 2라면

R일 경우, G일 경우,B일 경우로 나누어서 각각 내가 선택한 컬러를 제외한 나머지 2가지 경우에 대해 재귀호출을 수행한다.

다만 무작정 재귀호출을 돌리면 시간초과가 나기 때문에, 메모이제이션이 필요하다.

메모이제이션은

간단하게 mem[n][Color]에 값이 존재하는 경우 바로 리턴해주면 된다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;
constexpr int INF = INT_MAX;
constexpr int MAX = 1005;
constexpr int R = 0;
constexpr int G = 1;
constexpr int B = 2;
constexpr int RGBMAX = 3;
int mem[MAX][RGBMAX];
int RGB[MAX][RGBMAX];

int DP(int Color, int n)
{
	if (n <= 1)
	{
		return mem[n][Color];
	}
	if (mem[n][Color] != INF) return mem[n][Color];
	if (Color == R)
		mem[n][Color] = min(min(mem[n][Color], DP(G, n - 1) + RGB[n][Color]),DP(B,n - 1)+RGB[n][Color]);
	else if (Color == G)
		mem[n][Color] = min(min(mem[n][Color], DP(R, n - 1) + RGB[n][Color]),DP(B,n - 1)+RGB[n][Color]);
	else
		mem[n][Color] = min(min(mem[n][Color], DP(R, n - 1) + RGB[n][Color]), DP(G, n - 1) + RGB[n][Color]);
	return mem[n][Color];
}
int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(0);
	int n, r, g, b, MIN = INF;
	cin >> n;
	for (int i=0; i<MAX; i++)
	fill_n(mem[i], RGBMAX, INF);

	for (int i = 1; i <= n; i++)
	{
		cin >> r >> g >> b;
		RGB[i][R] = r;
		RGB[i][G] = g;
		RGB[i][B] = b;
	}
	mem[1][R] = RGB[1][R];
	mem[1][G] = RGB[1][G];
	mem[1][B] = RGB[1][B];
	for (int i = 0; i < RGBMAX; i++)
	{
		DP(i, n);
	}
	cout << min(min(mem[n][R], mem[n][G]), mem[n][B]);
}

처음 시작할때 R, G, B 3가지 경우로 칠하는 방법이 있으므로 반복문 3번을 통해 각각의 경우를 수행해주면 된다.