[Baekjoon] 1149번: RGB거리

 

 

 

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

1149번: RGB거리

 

---

 

문제 해결 과정

착안

$N$ 번째 단계에서 $N$ 번째 집을 색칠할 때, 빨강, 초록, 파랑 중 $i$ 번째 색깔로 칠하려면 $(N-1)$ 번째 집이 $i$ 번째 색깔이 아니어야 한다. 한편 $N$ 번째 집을 색칠하는 비용이 최소가 되기 위해서는 $(N-1)$ 번째 단계의 집까지도 역시 최소 비용으로 색칠을 해야한다. 즉, $N$ 번째 집을 $i$ 번째 색깔로 칠하는 비용을 $c_{i}$, $N$ 번째 집을 $i$ 번 색깔로 색칠하기 위한 최소 비용을 $f_{i}(N)$라고 하면

 

$$f_{i}(N) = c_{i} + \min_{j \neq i}  f_{j}(N-1)$$

 

이다. 이때 $i$ 번째 색을 제외한 나머지 두 색 중에서 $N-1$ 번째 집을 어느 색으로 칠해야 최소 비용인지는 직접 계산을 해보기 전까지 알 수 없기 때문에 $f_{i}(N)$의 값을 구하기 위해서는 $f_{i}(N)$ 부터 $f_{i}(N)$ 까지 순차적으로 모두 계산해야 하므로 동적계획법(dynamic programming)을 통해 문제를 해결하고자 하였다.

 

구현

$N$ 번째 집을 $i$ 번째 색깔로 칠하는 단계에서 $f_{j}(N-1) (j \neq i)$의 최솟값을 찾기 위해 반복되는 코드는 규칙성과 나머지 연산자(%)를 활용해 줄여보았다.

 

한편, 중간 단계의 비용들은 다음 단계의 비용을 계산할 때 외에는 사용되지 않으므로, 계산 이후 메모리 절약을 위해 변수를 돌려쓰는 방식으로 동적계획법 코드를 구현하였다. 최종적으로 $i = 1, 2, 3$ 에 대해 $f_{i}(N)$의 값을 모두 구하면 가장 작은 값을 찾아 출력하여 문제를 해결하였다.

* 최대 단계 수가 $N \leq 1000$ 이므로 배열로 전부 저장해도 사실 메모리를 엄청나게 많이 쓰는 것은 아니다...

* 최솟값을 찾는 과정은 편의상 <algorithm> 헤더의 min_element() 메서드 사용.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int N, Total[3] = { 0, }, Subtotal[3] = { 0, };
	cin >> N;

	int R, G, B;
	cin >> Subtotal[0] >> Subtotal[1] >> Subtotal[2];

	int costs[3] = { 0, };
	for (int i = 1; i < N; i++)
	{
		cin >> costs[0] >> costs[1] >> costs[2];
		
		for (int j = 0; j < 3; j++)
		{
			int idx1 = (j + 1) % 3, idx2 = (j + 2) % 3;
			Total[j] = costs[j] + (Subtotal[idx1] < Subtotal[idx2] ? Subtotal[idx1] : Subtotal[idx2]);
		}

		for (int j = 0; j < 3; j++)
			Subtotal[j] = Total[j];
	}

	cout << *min_element(&Total[0], &Total[2] + 1) << "\n";
	return 0;
}

 

실행 결과