[백준] 1149번. RGB거리

[백준] 1149번. RGB거리

1. 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

2. 입력

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

3. 출력

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

4. 풀이

• 흔한 DP문제였다.
• 각 줄마다 가장 적은 경우를 찾고 마지막 줄에서 그 중 가장 작은 것을 찾으면 된다.
• D[i][0] = arr[i][0] + min(D[i-1][1], D[i-1][2])를 이용하면 된다.
• 0이 아닌 경우도 똑같이 해주면 된다.

5. 처음 코드와 달라진 점

• 런타임 에러가 떠서 보니까 2차원 배열 선언할 때 행과 열을 반대로 해줬다. 근데 VS에서는 정상적으로 돌아갔다. 무서운 프로그램이다.

6. 코드

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

int arr[3][1000];
int d[3][1000];

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

	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
	}

	d[0][0] = arr[0][0];
	d[0][1] = arr[0][1];
	d[0][2] = arr[0][2];

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

	int minValue = d[n - 1][0];
	minValue = min(min(d[n - 1][1], d[n - 1][2]), minValue);
	cout << minValue;
	
}