[C++] 백준 1149번 RGB거리

1. 문제이해

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

1149번: RGB거리

 

집의 수(N)와 각 집을 빨강(R), 초록(G), 파랑(B)으로 칠하는 비용이 주어진다.

다음과 같은 조건을 만족하면서, 모든 집을 칠할 수 있는 최소비용을 구하는 것이 목표이다.

 

1. 1번 집의 색은 2번 집의 색과 같지 않아야 한다.

2. N번 집의 색은 N - 1번 집의 색과 같지 않아야 한다.

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

 

 

 

2. 문제풀이

 

위와 같은 조건을 만족하면서 모든 집을 칠하는 최소비용을 구하는 문제이다.

위 조건 3가지를 간단히 축약해보면 다음과 같다.

모든 집은 양 옆의 집과 색이 달라야 할 것

예를 들어, 2번째 집의 색을 R로 칠했다면, 양옆의 집인 1번째, 3번째 집은 R로 칠해서는 안된다는 것이다.

 

그렇다면, 위와 같은 조건을 만족하면서 모든 집을 칠하는 최소비용은 과연 어떻게 구해야 할까?

i번째 집을 R로 칠하는 경우를 생각해보자.

i번째 집을 R로 칠하면, 당연히 i - 1번째 집은 B또는 G로 칠했어야 할 것이다.

따라서, i번째 집을 R로 칠할 경우의 최소비용은

i - 1번째 집을 B로 칠했을 때의 최소비용 또는 G로 칠했을 때의 최소비용 중 더 작은 값에

현재 집인 i번째 집을 R로 칠하는 비용을 더한 것이 될 것이다.이를 식으로 나타내면 다음과 같다.

 

i 번째 집을 R로 칠할 경우의 최소 비용

= min(i - 1번째 집을 B로 칠했을 때의 최소비용, i - 1번째 집을 G로 칠했을 때의 최소비용)

+ i번째 집을 R로 칠하는 비용

 

i번째 집을 B, G로 칠하는 경우도 위와 같은 원리를 따른다.

위 식을 이용해 작성한 코드는 아래와 같다.

 

 

 

3. 소스코드

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

int main() {
	int N;                // 집의 수
	int R, G, B;          // 각 집을 R, G, B로 칠할 때의 비용
	int house[1001][3];   // 각 집을 R, G, B로 칠할 때의 최소비용
	int min_cost = 0;     // 모든 집을 칠하는 최소비용

	house[0][0] = 0;      // house[i][0] = i번째 집을 R로 칠할때의 최소비용
	house[0][1] = 0;      // house[i][1] = i번째 집을 G로 칠할때의 최소비용
	house[0][2] = 0;      // house[i][2] = i번째 집을 B로 칠할때의 최소비용

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> R >> G >> B;

		// i번째 집을 R로 칠할 경우의 최소비용
		//  = i-1번째 집을 G 또는 B로 칠할 때의 최소비용 
        	//    + i번째 집을 R로 칠하는 비용
		// (i번째 집을 G, B로 칠하는 경우도 위와 동일한 원리)
		house[i][0] = min(house[i - 1][1], house[i - 1][2]) + R;
		house[i][1] = min(house[i - 1][0], house[i - 1][2]) + G;
		house[i][2] = min(house[i - 1][0], house[i - 1][1]) + B;
	}

	// N번째 집을 R, G, B로 칠하는 경우 중 최솟값이 모든 집을 칠하는 최소비용
	min_cost = min({ house[N][0], house[N][1], house[N][2] });
	cout << min_cost;

	return 0;
}

위와 같이 변수들을 선언해준 뒤 house[0][0], house[0][1], house[0][2] 값을 0으로 초기화해준다.

(각각 0번째 집을 R, G, B로 칠하기 위한 비용인데, 우리는 1번째 집부터 취급하기 때문에 0으로 모두 초기화)

 

이후 for문을 통해 i번째 집을 각각 R, G, B로 칠할 때의 최소 비용을 계산해준다.

2. 문제풀이에서 도출해낸 식을 그대로 이용해주었다.

for문을 통해 마지막 집인  N번째 집까지 R, G, B로 칠하는 최소비용을 구하고 나면,

각 값들 중 최솟값이 모든 집을 칠하는 비용 중 최소비용이 되기 때문에 이들 중 최솟값을 구해준다.

 

 

---

오늘도 어김없이 다이나믹 프로그래밍 문제를 풀어보았다.

DP문제는 역시 초반에 식을 도출해내는게 가장 중요한것 같다🤔

그래도 뭔가 감이 조금 잡혀가는 것 같기도..?🥺