[백준] 1149번 RGB거리 (Python)

문제 풀이:

이 문항은 dp문항이다. 처음에 input을 arr list를 만들어 따로 받았는데, 그럴 필요가 없었다.

arr로 따로 만들게 된 이유는, 이때까지 풀었던 몇 가지 dp 문항들이 min(dp[i-1] + arr[i],dp[i]) 이런식으로 자꾸 비교하면서 들어오길래 이상하게 생각없이 arr를 무작정 만들었었다. 그런데 해결이 안되니, 근본적인 이유는, 그냥 R일 때 G일 때 B일 때를 모두.. dp로 해보면 된다는 점이었음. '모두'라 함은 작을 수 있는 가능성이 있는 경우를 뜻함.

 

그래서, 시작이 무엇이니에 따라서 case가 3가지가 나오고 그때마다 그냥 가장 적게 드는 값을 탐색하다보면 답이 나온다.

 

코드:

N = int(input())
dp = []

for _ in range(N):
    dp.append(list(map(int,input().split())))

for i in range(1,N):
    dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + dp[i][0]
    dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + dp[i][1]
    dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + dp[i][2]

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