[백준/BOJ] python 1149번 RGB거리

언어: python

번호: 1149

제목: RGB거리

등급: 실버1

 

​

풀이 과정:

​DP(동적계획법)으로 풀 수 있다. 집의 색깔은 빨강, 초록, 파랑 중에 하나로 칠해야 한다. 이때 i번째(1<i<n) 집을 한 색으로 칠하기 위해서는 i-1번째 집을 그 색을 제외한 나머지 색깔 중 비용이 적은 것으로 칠하면 된다.

i번째 집은 파랑 > i-1번째 집이 빨강 또는 초록 중에 비용이 적은 것

 i번째 집은 빨강 > i-1번째 집이 초록 또는 파랑 중에 비용이 적은 것

 i번째 집은 초록 > i-1번째 집이 파랑 또는 빨강 중에 비용이 적은 것

으로 칠하면 된다. 2차원 배열 DP[n][3]을 만들어 n번째 열에 n번째 집을 칠하는 색깔에 따라 생기는 비용의 총합을 저장해 가장 작은 값을 출력하면 된다. 

예제 입력 1

3
26 40 83
49 60 57
13 89 99

 

dp[n][3]	1번째	2번째	3번째	모든 집을 칠하는 비용
빨강	26	min(40, 83) + 49 = 89	min(96, 73) + 13 = 86	86
초록	40	min(26, 83) + 60 = 96	min(89, 73) + 89 = 162	162
파랑	83	min(26, 40) + 47 = 73	min(89, 96) + 99 = 188	188

 

 

코드:

# 1149
import sys
input = sys.stdin.readline

n = int(input())
dp = []

for i in range(n):
    dp.append(list(map(int, input().split())))

for i in range(1, n):
    dp[i][0] = dp[i][0] + min(dp[i-1][1], dp[i-1][2])
    dp[i][1] = dp[i][1] + min(dp[i-1][0], dp[i-1][2])
    dp[i][2] = dp[i][2] + min(dp[i-1][0], dp[i-1][1])

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