https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
동적 계획법을 사용해 푸는 문제로
optimal substructure를 잘 구성하면 금방 풀 수 있는 문제이다.
- RGB 비용을 cost[n][3] 배열에 저장한다.
- sum[n][3] 배열을 생성한다.
sum[i][color] : i번째 color 색 건물 까지의 건설 비용의 합
- cost[0]을 sum[0]에 복사한다 (table setup)
- 값이 계산된 i-1번째 행을 이용해 sum [i]행을 채운다. (table fill)
color와 같지 않은 두 색깔 c1, c2에 대해
sum[i][color] = min(sum[i-1][c1], sum[i-1][c2]) + cost[i][color]
cost
| 26 | 40 | 83 |
| 49 | 60 | 57 |
| 13 | 89 | 99 |
sum
| R | G | B | |
| sum[0] | 26 | 40 | 83 |
| min(sum[0][c1], sum[0][c2]) | 40 | 26 | 26 |
| sum[1] | 89 | 86 | 83 |
| min(sum[1][c1], sum[1][c2]) | 83 | 83 | 89 |
| sum[2] | 96 | 172 | 188 |
배운 내용 : optimal substructure은 1차원 배열이 아닐 수도 있다.
동적 계획법에서는 P[i]를 계산하기 위해
어떤 값들이 미리 계산되어 있어야 하는지를 판단해야 한다.
이번 문제에서는 현재 행에서의 최소 비용을 계산하기 위해
각 색깔마다 앞의 행까지의 최소 비용이 계산되어 있어야 하며,
따라서 substructure를 2차원 배열로 구성해야 한다.
'백준' 카테고리의 다른 글
| 백준 2579 - 계단 오르기 (0) | 2023.05.09 |
|---|---|
| 백준 1932 - 정수 삼각형 (0) | 2023.05.08 |
| 백준 1904 - 01타일 (0) | 2023.05.04 |
| 백준 10815 - 숫자 카드 (0) | 2023.05.03 |
| 백준 20920 - 영단어 암기는 괴로워 (0) | 2023.05.02 |