[백준 BOJ] 1149 : RGB거리 (C++)

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

1149번: RGB거리

아이디어 흐름

1. 아이디어 구상

문제의 조건이 앞의 색과 다른 색으로만 칠하면 된다는 의미이기 때문에

1. arr[1001][3] 배열을 선언한 후 각 집의 R, G, B 값을 모두 저장
2. 현재 i번째 인덱스를 진행중일 때, 점화식은 dp[i] = dp[i - 1] + min(arr[i][0], arr[i][1], arr[i][2])
3. 기저조건(초기값)이 가장 작은 값으로 시작한다고하여 뒤에 이어지는 값의 최종합이 최소가 된다는 보장이 없음

2. 초기 아이디어의 한계, 수정

위 아이디어의 3번을 어떻게 처리해야하나 고민하다가 결국 실패했다. 

1. dp배열 자체를 dp[i][0], dp[i][1], dp[i][2] 이렇게 각각 R, G, B 로 시작할 때에 대하여 모두 구해야겠다는 아이디어
2. 세 가지 경우에 대한 dp배열을 모두 구하는 중이므로 i번째 인덱스에서 색을 고르는 것이 아니라 고를 색을 고정해놓고 dp 배열에 min 을 걸어두는 아이디어

이 두 가지 아이디어를 생각해냈어야했다.

3. 코드

#include <iostream>
using namespace std;

int arr[1001][3];
int dp[1001][3];

int main() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 3; j++) cin >> arr[i][j];
	}

	// 첫 번째 집이 각각 R,G,B일 때에 대한 기저조건
	dp[0][0] = arr[0][0];
	dp[0][1] = arr[0][1];
	dp[0][2] = arr[0][2];
	
	for (int i = 1; i < N; i++) {
		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2];
	}
	cout << min(dp[N - 1][0], min(dp[N - 1][1], dp[N - 1][2])) << '\n';
}

4. 아쉬운 점

점화식을 세운 후 하나의 케이스로 전부 처리하려고 했는데, 위와 같이 같은 점화식을 여러 케이스로 나누어 모두 구한 후 최종 답을 도출할 수도 있다는 유연한 생각이 필요할 것 같다.