[백준] 1149번 RGB거리

사용 언어 - Python3

문제 -  1149번 RGB거리

https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

 

정답

바텀업 DP

손코딩, 아이큐 테스트, 규칙 찾기 문제

빨/초/파는 같은 rgb를 가진 집과 이웃하면 안되므로, 각 색깔을 기준으로 비용을 업데이트해준다.

빨 - 이전의 초 or 파 중 최솟값 +  현재의 빨 값

초 - 이전의 빨 or 파 중 최솟값 + 현재의  초 값

파 - 이전의 빨 or 초 중 최솟값 + 현재의  파 값

 

모든 집을 칠하는 비용의 최솟값 = 가장 마지막 행의 값 중 가장 작은 값 = min(price[n-1])

+ 인덱스 주의) 1부터 시작해야함!!! idx-1 이니까.

n = int(input()) # 집의 수
price = [list(map(int,input().split())) for _ in range(n)] # 빨,초,파 비용

for idx in range(1,n):
    for rgb in range(3):
        if rgb == 0: # 빨
            price[idx][0] = min(price[idx-1][1],price[idx-1][2]) + price[idx][0]
        if rgb == 1: # 초
            price[idx][1] = min(price[idx-1][0],price[idx-1][2]) + price[idx][1]
        if rgb == 2: # 파
            price[idx][2] = min(price[idx-1][0],price[idx-1][1]) + price[idx][2]

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

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/1149_rgb%EA%B1%B0%EB%A6%AC.py