백준 1149 RGB 거리

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 N개의 집을 칠 할 때 각각의 줄에 R G B의 색으로 칠하는 비용을 입력 받습니다. 이때 서로 이웃한 i-1과 i+1번째 집은 같은색을 칠할 수 없다는 제약이 있습니다. 따라서 각각의 색깔로 칠했 을때를 dp를 이용하여 모두 저장후 최종적으로 값들을 비교해서 가장 작은 값을 출력해야 합니다.

 

예를들어 i번째 집을 빨간색으로 색칠 한다면 i-1번째 집을 파란색으로 색칠하는 비용과 초록색으로 색칠하는 비용중 더 적은 비용을 선택하면 됩니다.

 

dp[0][i] = min( dp[1][i-1] + red[i], dp[2][i-1] + red[i]); 따라서 각 색깔마다 이러한 점화식이 만들어지게 됩니다.

 

dp에 각각의 색깔을 i번째 집에 칠할때의 비용들을 저장해야 하므로 2차원으로 선언하여 첫번째 인덱스는 색깔 i는 집의 번호를 나타냅니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int red[1001] = {0, };
	int blue[1001] = {0, };
	int green[1001] = {0, };
	int dp[3][1001] = {0, };
	int N; cin >> N;
	for(int i = 1; i <= N; i++) {
		cin >> red[i];
		cin >> blue[i];
		cin >> green[i];
	}
	dp[0][1] = red[1];
	dp[1][1] = blue[1];
	dp[2][1] = green[1];
	
	for(int i = 2; i <= N; i++) {
		dp[0][i] = min( dp[1][i-1] + red[i], dp[2][i-1] + red[i]); 
		dp[1][i] = min( dp[0][i-1] + blue[i], dp[2][i-1] + blue[i]); 
		dp[2][i] = min( dp[0][i-1] + green[i], dp[1][i-1] + green[i]); 
	}
	int result;
	result = min(dp[0][N], dp[1][N]);
	result = min(result, dp[2][N]);
	cout<< result;
	return 0;
}