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보다 작거나 같은 자연수이다.

풀이:

• 이 문제는 dp 배열에 최소 비용을 저장하면 되는 문제이다. 다이나믹 프로그래밍을 풀 때는 배열을 어떤 모양으로 만드는지도 중요한 것을 알게 되는 문제였다. 우선, 구분을 위해 2차원 배열이 필요하다. 우선, 제일 처음에는 dp에 자기 자신의 색을 저장한 뒤 이전 색깔이 다른 값들 중 최소값을 자신과 더한다. 그렇게 하여 R, G, B 모든 색깔의 최소 비용을 계산 한 뒤 마지막에 R, G, B중 최소값을 출력 해준다.

코드:

#include <iostream>
#define R 0
#define G 1
#define B 2

using namespace std;

int main(){
	int n;
	//입력
	cin >> n;
	long long dp[n][3];
	for(int i = 0; i < 3; i++) cin >> dp[0][i]; //dp[0][#] 값 초기화
	for(int i = 1; i < n; i++){
		cin >> dp[i][R] >> dp[i][G] >> dp[i][B]; //자신의 값 입력
		//같지 않은 색깔 중 최소 값을 자신과 더함
		dp[i][R] += min(dp[i-1][G],dp[i-1][B]);
		dp[i][G] += min(dp[i-1][R],dp[i-1][B]);
		dp[i][B] += min(dp[i-1][R],dp[i-1][G]);
	}
	//출력
	cout << min(dp[n-1][R],min(dp[n-1][G], dp[n-1][B]));
}