백준 알고리즘 - RGB 거리 (1149번)[Python]

문제

문제 상황

- 선택에 일종의 무게(가격)이 존재한다. 

- 선택지가 여러가지이고 선택마다 대소가 바뀌어 최선의 선택을 해야한다. 

 

해결 전략

- DP를 이용해 해결하는데 가격이 최대가 아니라 최소이므로 min을 이용하여 해결한다. 

코드 

n = int(input())
RGB = [[] for _ in range(n+1)]
for i in range(1,n+1):
    r,g,b = map(int, input().split())
    RGB[i] = [r,g,b]
for i in range(2, n+1):
    RGB[i][0] = min(RGB[i-1][1], RGB[i-1][2]) + RGB[i][0] # red
    RGB[i][1] = min(RGB[i-1][0], RGB[i-1][2]) + RGB[i][1] # green
    RGB[i][2] = min(RGB[i-1][0], RGB[i-1][1]) + RGB[i][2] # blue
print(min(min(RGB[i][0],RGB[i][1]),RGB[i][2]))

해설

 경우의 수가 3가지 이므로 선택에 따라 2가지 경우의 수가 생긴다. 이를 Bottom-Up으로 각 선택에서 최소가 될 때를 선택해 나아간다.  

새로 학습한 것 & 실수

- 조금씩 이해가 가고 있지만 아직 문제를 완벽히 해결할 수가 없다. 

- 중요한 것은 어떤 선택이 선택지를 좁히고, 이것이 반복되어 주어진 조건을 찾아야 하는 상황에서 DP를 써야 한다는 것이다.