TIL 61 | 동적계획법 RGB거리 (백준 1149 python)

🚀문제 바로가기

접근방식

'개념은 알겠는데 그래서 어떻게 적용해야 하는거지..?' 싶던 흐릿함이 문제를 풀수록 선명해지고 있다.

동적계획법, 다이나믹프로그래밍 DP

다이나믹프로그래밍은 이전 계산 결과를 저장하여 계산량을 줄여준다. 1부터 N까지 N번의 연산을 해야하는 문제도 N과 N-1만을 계산할 수 있도록 한다. N-1에는 N-2까지, N-2에는 N-3까지가 이미 반영되어 있기 때문이다. 현재시점인 N과 그 직전인 N-1만 비교하면 된다.

집마다 빨강, 초록, 파랑을 칠했을 때의 비용을 한 쌍으로 하여 저장한다. 첫 집의 데이터를 dp[0]으로 사용한다면 그 다음 집의 비용을 계산할 때는 이전 집의 비용을 고려하며 계산해나간다. N번째 집이 빨강을 칠한다면 N-1번째 집은 초록 또는 파랑으로 칠해져 있어야 한다. 그렇다면 N번째 집의 빨강 칠 비용에 이전 집의 초록 칠 비용, 파란 칠 비용 중 더 적은 비용을 합산하여 저장한다. dp[-1]을 활용해 마지막 집까지 계산을 마쳤다면 마지막 집의 비용은 모든 집의 선택지가 반영된 누적 최소 비용이다. 마지막 집이 빨강을 택했을 때의 누적 최소 비용, 초록을 선택했을 때의 누적 최소 비용, 파랑을 선택했을 때의 누적 최소 비용이 R,G,B로 저장되어 있을 것이다. 그렇다면 R,G,B 중에서도 가장 최소가 되는 비용을 택하면 된다.

정답코드

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

r,g,b = [int(x) for x in input().split()] #첫번째 입력값은 dp에 바로 저장
dp.append((r,g,b))
for _ in range(1,n):
	r,g,b = [int(x) for x in input().split()]
    pR,pG,pB = dp [-1] #이전 계산 결과(dp[-1])를 활용
    R = r+min(pG,pB)
    G = g+min(pR,pB)
    B = b+min(pR,pG)
    dp.append((R,G,B))

print(min(dp[-1]))