💡문제를 처음 보고 든 생각

처음 문제를 보고 예외 처리를 어떤식으로 해야할 지 전혀 감이 잡히지 않았습니다. 그동안 다이나믹 프로그래밍에서는 다양한 경우들을 새로운 자료구조를 만들어 저장한 뒤 꺼내 쓰는 방식이었기 때문에 계속 그러한 방향성으로 생각했습니다. 그래서 검색을 해보았고 코드를 자세히 보기 전 코드 길이를 보고 이렇게 짧게 코딩이 가능한 문제였구나 싶었습니다.

🔨트러블 슈팅

참고 블로그
이 문제 역시 메모이제이션을 사용해 이전의 값들을 저장한 뒤 재사용하는 다이나믹 프로그래밍으로 해결 가능한 문제입니다. 하지만 기존에 풀었던 문제들과는 다르게 값들이 전부 주어지고 해당 값을 변화시키면서 메모이제이션을 진행해야 합니다. 이게 무슨 말이냐면, 기존의 문제들은 f(10)의 값을 구한다고 가정했을 때 f(9), f(8)의 값을 어떤 배열 array[9], array[8]로부터 가져와서 문제의 공식에 맞도록 f(10)의 값을 구했습니다. 하지만 이 문제는 미리 f(1)부터 f(10)까지의 값을 주고 주어진 값들의 조건에 맞는 최소합을 구하는 것 입니다. 특히 모든 경우 중에 최소를 구해야 하기 때문에 현재 위치한 인덱스의 값(이 문제에서는 거리에 해당)에 그 전까지의 최소 합을 더한 값을 다시 현재 위치한 인덱스 값에 대입을 해주면 현재 위치에는 처음 인덱스부터 현재 인덱스까지 더한 최소합이 저장됩니다. 결과적으로 마지막 인덱스에는 마지막에 R을 선택한 경우, G를 선택한 경우, B를 선택한 경우 총 3가지의 최소값이 저장됩니다. 이 중 가장 작은 값이 문제의 정답이 됩니다.

💻소스 코드

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N = int(input())
RGB_street = []

for i in range(N):
    RGB_street.append(list(map(int,input().strip().split())))

# 0,1,2를 R,G,B로 표현
for i in range(1, N):
    RGB_street[i][0] = RGB_street[i] [0]+min(RGB_street[i-1][1], RGB_street[i-1][2]) # 이전 집 중에 현재 색깔과 다르고 값이 작은 것을 선택
    RGB_street[i][1] = RGB_street[i][1]+min(RGB_street[i-1][0], RGB_street[i-1][2]) # 이전 집 중에 현재 색깔과 다르고 값이 작은 것을 선택
    RGB_street[i][2] = RGB_street[i][2]+min(RGB_street[i-1][0], RGB_street[i-1][1]) # 이전 집 중에 현재 색깔과 다르고 값이 작은 것을 선택

print(min(RGB_street[N-1]))