[파이썬] 백준 1149 : RGB거리 (실버1)

[파이썬] 백준 1149 : RGB거리 (실버1)

 

1149번: RGB거리

---

문제

---

풀이

방향성 생각

2차원 DP를 만들어서 현재 밟는 지점에 누적 비용이 얼마인지 업데이트 한다.

DP의 가로는 0 1 2, R G B를 배정한다.

n은 칠해야하는 집의 수. 출발점으로부터 거리라고 생각한다.

 

초기값은 arr의 첫부분과 동일하게 지정.

다음 DP의 R = 다음 arr R + min(G현재,B현재)

이런식으로 현재 밟은 색깔이 아닌 곳 2개의 비용의 중 최소값을 더해준다.

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()
n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int,input().split())))

dp = [[0,0,0] for _ in range(n)]
dp[0] = arr[0]

for dist in range(n-1):
    for color in range(3):
        if color == 0 :
            dp[dist+1][0] = arr[dist+1][0] + min(dp[dist][1],dp[dist][2])
        elif color == 1 : 
            dp[dist+1][1] = arr[dist+1][1] + min(dp[dist][0],dp[dist][2])
        elif color == 2 : 
            dp[dist+1][2] = arr[dist+1][2] + min(dp[dist][1],dp[dist][0])
print(min(dp[-1]))

 

코멘트

DP 슬슬 풀린다