Dynamic Programming(DP) - RGB거리[1149]

초기 실패 소스코드

import copy

N = int(input())

nRGB = []
for i in range(N):
    RGB = list(map(int, input().split()))
    nRGB.append(RGB)

result = []
for i in range(3):
    temp = []
    idx = i
    copyRGB = copy.deepcopy(nRGB)
    sumResult = copyRGB[0][i]
    for RGB in copyRGB[1:]:
        RGB[idx] = 1000
        temp.append(min(RGB))
        sumResult += min(RGB)
        idx = RGB.index(min(RGB))
        
    result.append(sumResult)
print(min(result))

 

앞의 색과 겹치지 않는 나머지 색 중에서 가장 비용이 작은 색을 현재 집의 색으로 정하도록 했다.

하지만 이러면 현재는 최소 비용이지만 이후에 다른 집의 비용으로 인해 결과적으로는 최소 비용이 되지 않는 경우가 생긴다.

 

71	39	44
32	83	55
51	37	63
89	29	100
83	58	11
65	13	15
47	24	29
60	66	19

 

-> 합계 : 310

 

71	39	44
32	83	55
51	37	63
89	29	100
83	58	11
65	13	15
47	25	29
60	66	19

 

3번째에 37대신 63을 선택함, 7번째에 29대신 47을 선택함

-> 합계 : 253

성공 소스코드

import copy

N = int(input())

nRGB = []
for i in range(N):
    RGB = list(map(int, input().split()))
    nRGB.append(RGB)

for i in range(1, N):
    nRGB[i][0] =  nRGB[i][0] + min(nRGB[i-1][1], nRGB[i-1][2])
    nRGB[i][1] =  nRGB[i][1] + min(nRGB[i-1][0], nRGB[i-1][2])
    nRGB[i][2] =  nRGB[i][2] + min(nRGB[i-1][0], nRGB[i-1][1])
    
minNum = min(nRGB[N-1][0], nRGB[N-1][1], nRGB[N-1][2])
print(minNum)

이번 DP문제 역시 Bottom - Up 방식이다.

그런데 이전 집의 색을 결정하고 다음 집을 결정했던 이전 소스코드와 달리 이번에는 생각을 전환하여 현재의 집이 R, G, B 각각의 경우에 따라 최소 비용이 드는 이전의 집을 결정하는 것이다.

 

즉, 현재의 값에 따라 이전값을 결정하면서 마지막 집이 R, G, B 각각인 경우에 얼마의 최소비용이 드는지 계산하는 것이다.