Problem 1149

RGB거리

문제

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

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

입력

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

출력

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

문제 링크

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

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

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 번째 집까지의 최소 비용에 현재 올 수 있는 색을 칠하는 비용을 추가한다.

코드 설명

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

int rgb[1001][3];
int d[1001][3]; // d[i][j] = i번 집을 색 j로 칠했을 때, 1~i번 집을 칠하는 비용의 최솟값

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) // 각 집의 색깔별 비용 입력
		for (int j = 0; j < 3; j++)
			cin >> rgb[i][j];

	for (int i = 1; i <= n; i++) // 현재까지의 최소 비용에 현재 색깔 비용을 추가
	{
		d[i][0] = min(d[i - 1][1], d[i - 1][2]) + rgb[i][0]; // r의 앞에 올 수 있는 것은 g, b
		d[i][1] = min(d[i - 1][0], d[i - 1][2]) + rgb[i][1]; // g의 앞에 올 수 있는 것은 r, b
		d[i][2] = min(d[i - 1][0], d[i - 1][1]) + rgb[i][2]; // b의 앞에 올 수 있는 것은 r, g
	}

	cout << min({ d[n][0], d[n][1], d[n][2] }) << '\n';
}

백준 1149번 RGB거리

Baekjoon algorithm