백준 1149번: RGB거리

 

예제

 

풀이

 이 문제는 다이나믹 프로그래밍(DP) 기법을 통해 쉽게 풀 수 있다. 예제를 보면, 각 줄마다 i번째 집을 빨강으로 칠했을 때, 초록으로 칠했을 때, 파랑으로 칠했을 때 비용이 입력 값으로 들어온다. 먼저 입력값을 dp[1001][3] 배열에 저장한다. dp[0][0]은 0번째 집을 빨강으로 칠했을 때 비용, dp[0][1]은 0번째 집을 초록으로 칠했을 때 비용, dp[0][2]는 0번째 집을 파랑으로 칠했을 때 비용을 의미한다.

 

 입력이 끝난 다음, 다이나믹 프로그래밍(DP) 기법을 통해 이웃하는 집과 색이 겹치지 않도록 칠했을 때의 최소 비용을 구한다. for문을 돌면서 i번째 집에서 3가지 색깔로 칠했을 때의 최소 비용을 각각 계산해 dp[i][0] ~ dp[i][2]에 다시 저장한다. dp[i][0]의 최소 비용을 구한다고 가정한다면, dp[i-1][1]과 dp[i-1][2] 중에 최소값과 dp[i][0] 값을 더해 dp[i][0]에 저장하도록 한다. 결과적으로 dp[N][0] ~ dp[N][2] 중에 가장 작은 값이 우리가 구하고자 하는 최소 비용이 된다.

 

 

코드

#include <iostream>
#include <algorithm>
#define MAX 1001

using namespace std;

int dp[MAX][3];
int N, sum = 0;

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

int main() {
	init();

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> dp[i][j];
		}
		
		if (i == 0) continue;
		dp[i][0] = (dp[i - 1][1] < dp[i - 1][2]) ? dp[i][0] + dp[i - 1][1] : dp[i][0] + dp[i - 1][2];
		dp[i][1] = (dp[i - 1][0] < dp[i - 1][2]) ? dp[i][1] + dp[i - 1][0] : dp[i][1] + dp[i - 1][2];
		dp[i][2] = (dp[i - 1][0] < dp[i - 1][1]) ? dp[i][2] + dp[i - 1][0] : dp[i][2] + dp[i - 1][1];
	}

	int sum = (dp[N - 1][0] < dp[N - 1][1]) ? dp[N - 1][0] : dp[N - 1][1];
	sum = (sum < dp[N - 1][2]) ? sum : dp[N - 1][2];
	cout << sum;

}