[BOJ] 백준 1149 RGB 거리

문제

1149번: RGB거리

 

문제 해석

접근 방법

DP(Dynamic Programing)을 사용해 풀 수 있는 문제입니다.

 

풀이 과정

DP 문제는 점화식을 도출하는 것, 즉 이전 단계에 계산한 값을 어떤 방식으로 활용할 수 있을 지 생각하는 것이 중요합니다.

 

이번 문제의 경우 인접한 칸에 같은 색깔을 선택할 수 없다는 조건이 있습니다. 따라서 각 색깔을 선택했을 때 얻을 수 있는 최소 누적 비용을 계산해서 배열에 저장한 후, 다음 칸의 누적 비용을 계산할 때는 이전 단계에서 내 색깔과 다른 색깔을 선택한 경우 중 누적 비용이 가장 작은 것을 더해주면 됩니다.

 

마지막 단계까지 계산이 끝났다면 배열의 가장 마지막 인덱스에 각 선택지의 최소 비용이 저장되어 있을 것입니다. 이 중 가장 작은 값이 문제에서 요구하는 최소 비용입니다.

 

점화식

\[
\begin{align*}
\text{memo}[i][0] & += \min(\text{memo}[i-1][1], \text{memo}[i-1][2]) \\
\text{memo}[i][1] & += \min(\text{memo}[i-1][0], \text{memo}[i-1][2]) \\
\text{memo}[i][2] & += \min(\text{memo}[i-1][0], \text{memo}[i-1][1])
\end{align*}
\]

 

전체 코드

from sys import stdin

N = int(stdin.readline().rstrip())
memo = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

for i in range(1, N):
    # 각 색깔을 선택했을 때 얻을 수 있는 최소 누적 비용 계산
    memo[i][0] += min(memo[i-1][1], memo[i-1][2])
    memo[i][1] += min(memo[i-1][0], memo[i-1][2])
    memo[i][2] += min(memo[i-1][0], memo[i-1][1])
    
print(min(memo[-1]))