Problem 17404

RGB거리 2

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집도 이웃이다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로, 초록으로, 파랑으로 칠하는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

문제 링크

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

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

110

solve

점화식 d[i][j] = i번 집을 색 j로 칠했을 때, 1~i번 집을 칠하는 비용의 최솟값
- j = 0 : red
  - 앞에 올 수 있는 색 : green(1), blue(2)
- j = 1 : green
  - 앞에 올 수 있는 색 : red(0), blue(2)
- j = 2 : glue
  - 앞에 올 수 있는 색 : red(0), green(1)
각 색깔 별로 i - 1 번째 집까지의 최소 비용에 현재 올 수 있는 색을 칠하는 비용을 추가한다.
RGB거리 문제와 거의 동일하지만 첫 번째 집과 마지막 집이 서로 이웃인 조건이 추가되었다.
- 즉, 원형 문제가 되었다.
첫 번째 집의 색깔을 고정시킨 후 모든 경우를 구한 뒤 마지막 집에서의 최솟값을 첫 번째 집에서 고정시킨 색깔k를 제외하고 구한다.
이 과정을 k가 0 : red, 1 : green, 2 : blue 의 경우를 각각 반복하며 모든 경우의 최솟값을 구한다.

코드 설명

#include<iostream>
#include<algorithm>
using namespace std;
int d[1001][3]; // d[i][j] = i번째 집까지 모든 집을 칠하는 비용의 최솟값, j는 이번에 색칠할 집의 색깔
int rgb[1001][3];
int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 3; j++)
			cin >> rgb[i][j];

	int ans = 1000 * 1000 + 1; // 모든 경우보다 큰 값

	for (int k = 0; k <= 2; k++) // 첫 번째 집의 색깔 k(1:red, 2:green, 3:blue)
	{
		for (int i = 0; i <= 2; i++)
		{
			if (i == k)
				d[1][i] = rgb[1][i]; // 현재 색깔을 첫 번째 집 색깔로 고정
			else
				d[1][i] = 1000 * 1000 + 1;
		}

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

		// 첫번째 집 색깔이 k인 경우 마지막 집은 k가 아닌 색깔이 가능
		for (int i = 0; i <= 2; i++)
		{
			if (i == k) continue; // k 인경우 건너뜀
			ans = min(ans, d[n][i]); // 나머지 경우의 최솟값을 구함
		}

	}

	cout << ans << '\n';
}

백준 17404번 RGB거리 2

Baekjoon algorithm