https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
문제 해결 과정
착안
$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;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 1018번: 체스판 다시 칠하기 (0) | 2023.06.04 |
---|---|
[Baekjoon] 25192번: 인사성 밝은 곰곰이 (0) | 2023.06.04 |
[Baekjoon] 1197번: 최소 스패닝 트리 (0) | 2023.05.31 |
[Baekjoon] 11659번: 구간 합 구하기 4 (0) | 2023.05.30 |
[Baekjoon] 16236번: 아기 상어 (0) | 2023.05.30 |
댓글