백준 1149 - RGB거리

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

1149번: RGB거리

동적 계획법을 사용해 푸는 문제로

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차원 배열로 구성해야 한다.