뚝딱뚝딱

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

💡 RGB거리

[문제]
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

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

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

✅ 문제 풀이

이 문제는 전형적인 DP 문제이다.

집은 R,G,B 세 색상 중 하나로 칠할 수 있는데, 인접한 집끼리는 색이 겹쳐서는 안된다.

그렇게 칠했을 때 모든 집을 칭하는 최소 비용을 구한다.

일단 입력으로 주어지는 각 집당 페인트 비용을 저장하기 위해서 2차원 배열을 사용해보자.

문제에서 주어진 예시를 사용할 것이다.

행은 집의 번호, 열은 각 집의 R,G,B 비용이다.

첫번째 집까지 칠했을 때는 첫번째 집에서 고른 비용이 저장되는 것이고, 두번째 집까지 칠했을 때는 첫번째 집까지 쓰인 비용+두번째 집에서 고른 비용으로 값이 정해진다. 따라서 다음과 같은 점화식을 따른다.

d[i]=d[i-1]+a[i]

그런데, 비용을 최소로 한다고 해서 모든 집에서 가장 작은 비용을 선택해버린다면, 위 예에 따르면 26, 49, 13이 가장 최소가 되어버리고, 모두 빨간색으로만 칠하게 되어버린다. 이는 조건을 위배하게 된다.

따라서 이전 집에서 어떤 색을 칠했는지에 따라서 이번 집에 칠할 수 있는 색이 2개로 추려져야 한다.

그러므로 이전 집을 R로 칠했을때, G로 칠했을때, B로 칠했을때를 모두 계산하고 나서, 최종 집까지 칠했을때 세 값중 최소값이 답이 될 수 있다.

이때 현재 집(i번 집)에 R을 칠하고자 한다면 이전집(i-1)이 G또는 B가 칠해졌어야 하고, 이 둘 중 최소 비용에 현재 집의 R 비용을 더한 값이 d[i][0]이 될 수 있다.

이를 점화식으로 나타내면 다음과 같다.

d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0]; 
d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];

점화식에 따르면 위 표와 같이 정리될 수 있고, 이는 i번째 집까지 칠했을 때의 비용을 나타낸다.

따라서 위 예시의 답은 3번째 집까지 칠했을 때의 비용 96,172,146 중에 최소값인 96이 되는 것이다.

min(min(d[t][0], d[t][1]), d[t][2])

이 식을 통해서 답을 구할 수 있다. (t는 마지막 집의 번호이다)

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;

	vector<vector<int>> d(t + 1, vector<int>(3, 0));
	vector<vector<int>> a(t + 1, vector<int>(3, 0));

	for (int i = 1; i <= t; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2];
		d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0];
		d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
		d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];
	}

	int answer = min(min(d[t][0], d[t][1]), d[t][2]);

	cout << answer;

	return 0;
}