<dp> 백준 1149번. rgb거리 (실버 1)

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

1149번: RGB거리

1차 시도 :

"""
!!!!!!!!틀린 코드!!!!!!!!
"""
import copy
n = int(input())
lst = []
for _ in range(n):
  lst.append(list(map(int, input().split()))) #r,g,b
lst_ori = copy.deepcopy(lst)  

total = []
for i in range(3): #첫 번째 집을 빨강 초록 파랑 각각 선택한 경우 3
   dp = [0]*(n) #dp table
   dp[0] = lst[0][i] 
   idx = i 
   for j in range(1,n):
      lst[j][idx] = 1001 #예제 3 예외처리
      if idx == 0:
         dp[j] = dp[j-1] + min(lst[j][1], lst[j][2])
         idx= lst[j].index(min(lst[j][1], lst[j][2]))
         
      elif idx == 1:
         dp[j] = dp[j-1] + min(lst[j][0], lst[j][2])
         idx= lst[j].index(min(lst[j][0], lst[j][2]))     
      else:
         dp[j] = dp[j-1] + min(lst[j][1], lst[j][0])
         idx= lst[j].index(min(lst[j][1], lst[j][0]))  
  
      if j == n-1:
        total.append(dp[j])
        lst = copy.deepcopy(lst_ori)
 
print(min(total))

예제 1,2,3,4는 성공하였으나 예제 5번에서 답이 나오지 않음.. 글고 코드가 넘 더럽다..

 

그래서 그냥 버리고 처음부터 다시 생각했다.

n = int(input())
lst = []
for _ in range(n):
  lst.append(list(map(int, input().split()))) #r,g,b
# r,g,b
# 0,1,2 idx
for i in range(1,n):
  lst[i][0] = lst[i][0] + min(lst[i-1][1], lst[i-1][2])#현재 빨강(0)을 선택했으므로 idx-1 시점에서 min(파랑,초록) + 현재 빨강 값
  lst[i][1] = lst[i][1] + min(lst[i-1][0], lst[i-1][2])
  lst[i][2] = lst[i][2] + min(lst[i-1][0], lst[i-1][1])

print(min(lst[n-1][0], lst[n-1][1], lst[n-1][2]))

성공! 후...이런 깔끔한 코드가 있었는데 말이쥐..난 뭐했나 ㅠ