[동적계획법/DP] 백준 1149 RGB거리 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1149번: RGB거리

 

 

 

2. 문제 풀이

  옆집과 색이 같지 않도록 최소의 비용으로 색을 칠하는 문제입니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

  i번째 집을 빨강색, 초록색, 파란색으로 칠할 경우의 수를 모두 고려해야 합니다. 1번집부터 N번째집까지 차례차례 3가지 경우로 색을 칠할 때 드는 비용을 계산하고, 비교해서 최저요금을 찾아냅니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

#입력
N = int(input())
cost = []
for _ in range(N):
    cost.append(list(map(int, input().split())))

#DP
for i in range(1, N):
    # i번째 집을 빨강색으로 칠했을 때
    cost[i][0] = min(cost[i-1][1], cost[i-1][2]) + cost[i][0]

    # i번째 집을 초록색으로 칠했을 때
    cost[i][1] = min(cost[i-1][0], cost[i-1][2]) + cost[i][1]

    # i번째 집을 파란색으로 칠했을 때
    cost[i][2] = min(cost[i-1][0], cost[i-1][1]) + cost[i][2]
print(min(cost[N-1]))

 1번 집부터 N번째 집까지 반복문을 순회하며 각 경우에 대해 비용을 계산합니다.

 빨강색으로 칠할 경우, 이전 집(i-1번째 집)은 파란색 혹은 초록색이어야 하며 그 중 적은 비용과 현재 집(i번째 집) 도색비용을 더합니다.

 나머지 두 경우도 마찬가지로 계산한 뒤, N번째 집의 최소 비용을 구합니다.