[백준 1149] RGB거리

문제 링크 : https://www.acmicpc.net/problem/1149

1149번: RGB거리

총 N개의 집이 있을 때, i번째 집을 칠하는 경우의 수는 총 3가지이다. 

 

빨강, 파랑, 초록

 

---

 

똑같은 색은 이웃할 수 없다는 조건이 없다면 순서대로 가장 저렴한 색으로 칠하면 되지만

 

이웃한 집은 다른 색으로 칠해야 되므로 문제가 복잡해진다.

 

가장 먼저 빨간색으로 i번째 집을 칠하는 경우의 수를 생각해 보자.

 

i번째 집이 빨간색으로 칠해지지 위해서는 i-1번째 집이 초록색 또는 파랑색으로 칠해져 있어야 한다.

 

---

 

이는 곧 1~i-1번째 집까지 임의의 색으로 칠하고

 

i번째 집을 빨간색으로 칠하는 최소 비용은

 

(전에 있는 집들은 어떤 색으로 칠해져 있는지 알 필요는 없다)

 

1. 1~i-2번째 집까지 칠하고 i-1번째 집을 초록색으로 칠하는 최소 비용

 

2. 1~i-2번째 집까지 칠하고 i-1번째 집을 파란색으로 칠하는 최소 비용

 

위 두가지 경우 중 더 작은 비용에 i번째 집을 빨간색으로 칠하는 비용을 더하면 된다.

 

---

예를 들어서

 

10번째 집까지 칠하는데 드는 최소 비용은

 

(10번째 집은 빨간색으로 칠할 것이다. 비용은 10)

 

1. 9번째 집까지(9번째 집은 초록색) 칠하는 최소 비용인 99

 

2. 9번째 집까지(9번째 집은 파란색) 칠하는 최소 비용인 95

 

위 두가지 비용 중 더 작은 비용인 95에 10을 더한 105이다.

 

---

 

1번과 2번의 경우의 비용도 위에서 i번째 빨간색 집을 구하는 경우와 마찬가지로 구하면 된다.

 

물론 1번째 집까지 빨강,파랑,초록으로 칠하는 비용은

 

단순히 1번째 집을 빨강,파랑,초록으로 칠하는 비용이므로 1차적으로 구할 수 있다.

 

---

 

따라서 이 문제는 빨강, 파랑, 초록으로 분리된 3개의 DP배열을 채워나가는 문제이다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(void){
	int n;
	int house[3][1005];
	int dp[3][1005];

	cin >> n;

	for (int i = 0; i < n; i++){
		for (int j = 0; j < 3; j++){
			cin >> house[j][i];
		}
	}

	dp[0][0] = house[0][0];
	dp[1][0] = house[1][0];
	dp[2][0] = house[2][0];

	for (int i = 1; i < n; i++){
		dp[0][i] = min(dp[1][i - 1], dp[2][i - 1]) + house[0][i];
		dp[1][i] = min(dp[2][i - 1], dp[0][i - 1]) + house[1][i];
		dp[2][i] = min(dp[0][i - 1], dp[1][i - 1]) + house[2][i];
	}
	n -= 1;
	cout << min(min(dp[0][n], dp[1][n]), dp[2][n]) << endl;

	return 0;
}