[DP] 백준 RGB거리 1149번 with Python3

 

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

1149번: RGB거리

 

문제

정답 풀이

n = int(input())
p = []
for i in range(n):
    p.append(list(map(int, input().split())))

# 0,1,2 는 각각 빨강, 초록, 파랑을 뜻함.
for i in range(1, len(p)):
    p[i][0] = min(p[i - 1][1], p[i - 1][2]) + p[i][0]
    p[i][1] = min(p[i - 1][0], p[i - 1][2]) + p[i][1]
    p[i][2] = min(p[i - 1][0], p[i - 1][1]) + p[i][2]

# index 번호상 n-1이여야 리스트의 가장 끝 element
print(min(p[n - 1][0], p[n - 1][1], p[n - 1][2]))

출처:https://pacific-ocean.tistory.com/147

 

해석

아직까지도 dp 문제를 풀때 필요한 사고 방식을 갖추지 못했다. 자꾸 0에서 시작해서 앞으로 나아가는 식의 코드만 구상하게 되는데 대부분의 dp문제의 경우 이전 값을 활용하게 되기에 좀 더 사고를 유연하게 해야한다.