백준 1149번 : RGB거리 (Python)

문제 : www.acmicpc.net/problem/1149

1149번: RGB거리

 

풀이

다른 사람의 풀이를 참고했다.

 

dp에 값을 1개씩이 아닌 3개씩 저장한다.

반복문을 돌며 해당 위치(i)에서 R,G,B 로 각각 칠했을 때를 dp에 리스트로 저장한다.

즉 dp에는 지금까지 더한 값(dp) 중 i-1에서 R위치를 제외하고 가장 작은 값 + i에서 R로 칠할 경우를 B, G도 똑같이 수행한뒤 추가한다.

 

n = int(input())

cost = []

for i in range(n):
    a = list(map(int, input().split()))
    cost.append(a)

dp = []
dp.append(cost[0])

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

    dp.append(temp)

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