백준 1149 RGB거리 파이썬 문제풀이 (python 바텀업 DP)

문제 보러가기

 

백준 RGB거리 파이썬 문제풀이

 

RGB 빨강 초록 파랑 색 각각을 집집마다 칠하는 문제인데,

같은 색이 연속되지 않게 칠하면서 칠하는 비용을 최소화하는 문제이다.

 

비용은 각 집에 어떤 색을 칠하는지에 따라 다 달라서 입력으로 주어진다.

이걸 풀려면 현재 집을 칠하는 세 가지 방법 각각의 상황에서

이전 집까지 칠한 비용중 최소인 비용을 선택해서 칠하는 dp table을 만들어야한다.

 

정답 코드

n = int(input())
house = [list(map(int,input().split())) for _ in range(n)]
dp = [[0] * 3 for _ in range(n+1)]

for idx in range(n):
    for rgb in range(3):
        if rgb == 0: # red
            dp[idx][0] = min(dp[idx-1][1], dp[idx-1][2]) + house[idx][0]
        if rgb == 1:  # green
            dp[idx][1] = min(dp[idx - 1][0], dp[idx - 1][2]) + house[idx][1]
        if rgb == 2:  # blue
            dp[idx][2] = min(dp[idx - 1][0], dp[idx - 1][1]) + house[idx][2]

print(min(dp[n-1]))

rgb를 0,1,2 로 인덱싱하고

현재 집을 정했을 때 이전 집은 현재집과 다른 두 가지 색으로 칠하게 되는데,

이 두 가지 색 중 더 작은 비용을 가져와서 현재 집을 칠하는 비용을 더해서 저장한다.

 

 

맞았다~