[Baekjoon/Python] 1149번: RGB거리(Dynamic Programming)

 

# Baekjoon 1149번: RGB거리

import sys
input = sys.stdin.readline

N = int(input())
RGB = []
dp = [[0]*3 for _ in range(N+1)]

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

dp[0][0] = RGB[0][0]
dp[0][1] = RGB[0][1]
dp[0][2] = RGB[0][2]

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

print(min(dp[N-1][0], dp[N-1][1], dp[N-1][2]))

 

  이번 문제는 Dynamic Programming 알고리즘 문제이다. 동적 프로그래밍은 복잡한 문제를 해결하기 위한 알고리즘 설계 기법 중 하나로, 큰 문제를 여러 개의 작은 하위 문제로 나누어 해결한 뒤, 그 결과를 재사용함으로써 전체 문제를 효율적으로 해결하는 방법이다. 특히, 하위 문제들이 중복되어 여러 번 계산되는 경우 이를 저장해서 다시 계산하지 않도록 하는 메모이제이션(Memoization) 또는 테이블화(Tabulation)를 사용하여 성능을 향상시킨다. 알고리즘의 대표적인 예시 문제로는 피보나치 수열이 있다.

 

 이번 문제의 핵심 아이디어는 'N번째에 있는 집을 색칠할때의 최소 비용은 N-1번째까지 칠했을때의 최소 비용에 N번째 집을 색칠하는 비용을 합한 것과 같다'라는 생각이었다.

 

 DP 알고리즘은 점화식으로 문제를 이끌어내야하기 때문에 문제를 풀때 항상 관계식을 이끌어내도록 노력해야하는 것 같다.