BOJ 1149: RGB거리

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

---

알고리즘 분류 | 동적 계획법 (Dynamic Programming, DP)

풀이 |

각 집 별로 빨간색, 초록색, 파란색 순으로 비용이 들어온다. 그림으로 표현하면 다음과 같다.

예제 입력을 표현하면 이렇게 표현할 수 있다.

2차원 rgb 배열을 하나 만들어서 각 집마다 색 별로 칠할 때마다 발생하는 비용을 저장했고,
(0 = 빨간색, 1 = 초록색, 2 = 파란색)
dp 2차원 배열에 여태까지 칠한 비용의 최소값을 저장했다.

맨 처음 0번째 칸에는 최소비용은 물론 칠하는 비용도 없기 때문에
0으로 초기화해준다.

n번 째 집에 각 색별로 칠하는 비용을 생각하면 다음과 같다.

1. n번 째 집을 빨간색으로 칠한 경우
dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + rgb[n][0]
n번 째 집에 빨간색(0)으로 칠한 경우의 최소값을 저장하는 dp 배열에 n-1까지의 집을 칠할 때 발생한 비용의 최소값을 넣는데
이 때 n-1번째 집에는 빨간색으로 칠할 수 없기 때문에, 1번과 2번 값 중 최소값을 넣는다.
그리고 마지막으로 n번째 집에 빨간색을 칠하는 비용을 더해주는 것이다. 마찬가지로 초록색, 파란색을 칠할 때도 같다.

2. n번 째 집에 초록색으로 칠하는 경우
dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + rgb[n][1]

3. n번 째 집에 파란색으로 칠하는 경우
dp[n][2] = min(dp[n-1][0], dp[n-1][1])

이렇게 n번째 집을 칠하는 경우까지 모든 배열을 채워줄 수 있다.
마지막엔 n번째 집을 칠하는 색 중 최소 비용을 선택하여 출력한다.

소스 코드 |

#include <iostream>
using namespace std;
int dp[1001][3];
int rgb[1001][3];
#define min(a, b) ((a < b) ? a : b)

int main(void) {
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		int r, g, b;
		cin >> r >> g >> b;
		rgb[i][0] = r;
		rgb[i][1] = g;
		rgb[i][2] = b;
	}

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

	int ans = min(dp[n][1], dp[n][2]);
	ans = min(dp[n][0], ans);
	cout << ans << '\n';
	return 0;
}