[BOJ][Python]1149번 풀이

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

1149번: RGB거리

import sys
ssr = sys.stdin.readline

n = int(ssr())
cost = [list(map(int, ssr().split())) for _ in range(n)]
min_cost = [[0,0,0] for _ in range(n)]
min_cost[0] = cost[0]
for i in range(1,n):
    min_cost[i][0] = min(min_cost[i-1][1], min_cost[i-1][2]) + cost[i][0]
    min_cost[i][1] = min(min_cost[i-1][0], min_cost[i-1][2]) + cost[i][1]
    min_cost[i][2] = min(min_cost[i-1][0], min_cost[i-1][1]) + cost[i][2]
print(min(min_cost[-1]))

문제가 별로 안어려운데 왜 빨리 생각이 안나는지 모르겠습니다. 시간제한 0.5초에 정신이 팔렸는지 코드를 쓰기 보단 계속 생각만 하느라 오히려 더 그랬는지도 모르겠네요.

 

문제 접근은 일단 dp입니다. 다만 같은 색을 연속해서 선택할 수 없기 때문에 그 부분을 감안해서 코드를 작성해주셔야합니다. 제가 작성한 코드를 기준으로 설명을 드리자면 순서는 RGB로 0,1,2에 각각 할당되고 그 의미는 마지막으로 선택한 색에 따라 0,1,2를 나눴습니다. 따라서 메모이제이션을 하는 반복문의 의미는 직전에 선택한 색이 해당 인덱스가 아닌 두 값 중에 최솟값에 현재 선택한 색의 비용을 더하는 것입니다. 즉 min_cost[i][0] = min(min_cost[i-1][1], min_cost[i-1][2]) + cost[i][0] 은 '직전에 파란색이나 초록색을 선택했던 경우의 최소 비용 + 이번에 빨간색을 선택한 비용' 이 되는 것입니다(그 밑으로 초록, 파랑일 경우).