[파이썬] 17404 RGB거리 2 (백준)

문제 : 17404 - RGB거리 2 https://www.acmicpc.net/problem/17404

사용 언어 : 파이썬 (Pypy3)

 

문제 요약 :

서로 이웃하는 집과 첫 번째 집과 N 번째 집의 색이 같지 않다고 했을 때, 집의 색깔을 RGB로 칠하는 최소의 비용을 구하라.

---

해설 : 첫 집의 색깔을 정하고 (for문으로 다 해보기), 배열에 전 자신의 색깔을 제외한 두 색의 가격을 비교하여 최솟값을 자신에게 더하고 반복한다. 

더하는 과정

 

코드 :

import sys
input = sys.stdin.readline

#입력
N = int(input())
arr = [list(map(int,input().split())) for i in range(N)]

m = (1000+1)*N
ans = [m, m, m]
for t in range(3):
    dp = [[m, m, m] for j in range(N)]

    dp[0][t] = arr[0][t]
    #배열에 자신의 색상을 제외한 값을 더함
    for i in range(1, N):
        dp[i][0] = arr[i][0]+min(dp[i-1][1], dp[i-1][2])
        dp[i][1] = arr[i][1]+min(dp[i-1][0], dp[i-1][2])
        dp[i][2] = arr[i][2]+min(dp[i-1][0], dp[i-1][1])
    dp[-1][t] = m
    
    #마지막 집에서 가장 적은 값을 저장
    for x in range(3):
        ans[t] = min(ans[t], dp[-1][x])
        
print(min(ans))

---

 

앞으로 코딩과 알고리즘 관련 글을 업로드할 예정입니다!

아직 배우는 중이라서 부족한 점이 있으면 댓글 남겨주시면 감사하겠습니다!!