1149. RGB거리

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

 

 

처음에는 이게 왜 동적 프로그래밍인지 모르겠어서 해결방법이 보이질 않았다.

현재 R을 선택했을 때와 G, B를 선택했을 때의 결과를 각각 따로 저장해야된다고는 생각했는데

막연히 생각하기에 그렇게 하면 시간이 너무 오래 걸릴 것 같았다.

하지만 그렇게 해도 한 번 돌 때마다 3개의 계산을 한꺼번에 하므로, N의 시간밖에 걸리지 않는다는 것.

for문 안쪽의 의미는 다음과 같다.

• i번째에 R 색깔을 칠했을 때의 누적 비용 (0~i-1까지 무언가를 칠하고, i번째에 R을 칠했을 때의 모든 비용) =
• i번째에 R색깔을 칠하는 데 드는 비용 (이번만 칠하는 데 드는 비용) +
• i-1번째에서 G 혹은 B 색깔로 칠하는데 들었던 비용 중 최솟값(이 값 역시 누적된 비용이다)

import sys
N = int(sys.stdin.readline())
cost = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 입력(색칠비용)
val = [[0,0,0] for _ in range(N)]  # 계산될 색칠 비용 결과
R = 0
G = 1
B = 2

val[0][R] = cost[0][R]
val[0][G] = cost[0][G]
val[0][B] = cost[0][B]

for i in range(1, N):
    val[i][R] = cost[i][R] + min(val[i-1][G], val[i-1][B])
    val[i][G] = cost[i][G] + min(val[i-1][R], val[i-1][B])
    val[i][B] = cost[i][B] + min(val[i-1][G], val[i-1][R])

print(min(val[N-1][R], val[N-1][G], val[N-1][B]))  # 0부터 시작이므로 N-1