백준 1149번 RGB거리 (C++)

1149번: RGB거리

문제 분석

문제는 (1) 모든 집을 칠하는 최솟값을 구하고자 한다.

 

N개의 집이 순서대로 있고, i번째 집을 기준으로 i - 1번째, i + 1번째 집은 i번째와 색이 같지 않아야 한다. 

(2) 즉, 내 집과 양 옆집의 색이 겹치지만 않으면 된다.

 

집마다 칠할 수 있는 빨, 초, 파 색의 가격이 각각 주어지고, 이의 최솟값을 구해야한다.

🤫 : 음... 각 집마다 칠할 수 있는 가장 싼 색을 고르면, 옆 집이랑 겹칠수도 있고... 그렇다고 안겹치는 색의 경우의 수는 워낙 많으니... 어떻게 해야할까??

---

문제 풀이

DFS, BFS 등의 풀이도 가능하겠지만, 이 문제에서는 'DP'로 해결해야한다.

 

만약에, 집의 수가 최대로 주어지고 (1000개의 집) 이를 DFS로 계산하면, 3^1000이라는 가지수를 계산해야한다.

심지어 양 옆의 집 색은 겹치면 안되는 걸 제외하면, 시간복잡도는 매우 오래 걸릴것이다. 

 

이에, DP를 통해 패턴을 파악하여 최적의 계산을 실행해보자!

 

DP는 패턴파악을 하고 구현하는 것이 중요하다. 이에 직접 집의 색을 칠해보면서 패턴을 파악해보자.

 

1. 1번째 집이 빨간색 (index 0)일 때
   1) 1번째가 빨간색 (index 0)이다. 2번째 집은 초록색(index 1)과 파란색(index 2)을 칠할 수 있다.
   2) 2번째를 초록색 (index 1)이라 하자. 3번째 집은 빨간색(index 0)과 파란색(index 2)을 칠할 수 있다.
   3) 3번째를 파란색 (index 2)이라 하자. 4번째 집은 빨간색(index 0)과 초록색(index 1)을 칠할 수 있다.
   
   
2. 1번째 집이 초록색 (index 1)일 때
   1) 1번째가 초록색 (index 1)이다. 2번째 집은  빨간색(index 0)과 파란색(index 2)을 칠할 수 있다.
   2) 2번째를 파란색 (index 2)이라 하자. 3번째 집은 빨간색(index 0)과 초록색(index 1)을 칠할 수 있다.
   3) 3번째를 빨간색 (index 0)이라 하자. 4번째 집은 파란색(index 2)과 초록색(index 1)을 칠할 수 있다.
   
   
3. 1번째 집이 파란색일 때...

무언가 패턴이 보이지 않나요?

 

현재 집에 칠한 색의 index를 다음 집에서는 제외한 채 나머지 두 색의 index만을 고려해야한다! 
현재 index 0 : 다음 index 1 or 2
현재 index 1 : 다음 index 0 or 2
현재 index 2 : 다음 index 0 or 1

 

 

2개의 색 중 더 싼 색을 고르게 된다면 비용의 최솟값을 구한 것이다!

 

⚠️단! 처음 고르는 색을 가장 싸다고 꼭 최솟값은 아니니, DP를 활용하여 최솟값에 대한 DP 배열을 만들어라! ⚠️

 

 

ex) 예제어서 주어진 입력값이 1번 그림, DP 배열에 대해 최솟값만을 모은 것이 2번 그림

26	40	83
49	60	57
13	89	99

 

 

1. 0번째 행에서는 최소합이 자신밖에 없다

26	40	83

 

 

2. 1번째 행의 최소합은 겹칠 수 있다. ex) 현재 배열의 [1][0]에는 49(R) + 40(G)과 49(R)+ 83(B) 2개가 들어울 수 있다. 

이 때, 두 값중 가장 작은 값이 배열을 차지할 수 있다!

26	40	83
89	86	83

 

 

3. 2번처럼 다시 한번 수행하면 끝에 조합의 최솟값들이 쭉 나열된다.

26	40	83
89	86	83
96	172	185

 

 

현재 집에 칠할 색을 기준으로, 나머지 두 색중에 싼 색이 현재 색과 합쳐져 배열을 차지한다!

C++ 풀이

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;

	vector<vector<int>> house(N, vector<int>(3, 0));
	vector<vector<int>> DP(N, vector<int>(3, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> house[i][j];
		}
	}

	for (int i = 0; i < 3; i++) {
		DP[0][i] = house[0][i];
	}

	for (int i = 1; i < N; i++) {

		for (int j = 0; j < 3; j++) {
			if (j == 0) {
				if (DP[i - 1][1] > DP[i - 1][2]) 
					DP[i][j] = house[i][j] + DP[i - 1][2];
				else
					DP[i][j] = house[i][j] + DP[i - 1][1];
			}
			else if (j == 1) {
				if (DP[i - 1][0] > DP[i - 1][2])
					DP[i][j] = house[i][j] + DP[i - 1][2];
				else
					DP[i][j] = house[i][j] + DP[i - 1][0];
			}
			else {
				if (DP[i - 1][0] > DP[i - 1][1])
					DP[i][j] = house[i][j] + DP[i - 1][1];
				else
					DP[i][j] = house[i][j] + DP[i - 1][0];
			}
		}
	}

	int min = 100000000;
	for (int i = 0; i < 3; i++) {
		if (min > DP[N - 1][i])
			min = DP[N - 1][i];
	}

	cout << min;

	return 0;
}

코드 리뷰는 언제나 환영입니다!