[Python] 백준 1149. RGB거리

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

1149번: RGB거리

DP 점화식을 세워서 해결할 수 있는 문제.

 

각 집마다 R, G, B 색깔로 칠할 때의 비용이 주어지므로, idx 0 = R, 1 = G, 2 = B로 정의하면

 

0 <= j < 3인 j에서

dp[i][j] = i번째 집을 idx j 색깔로 칠할 때 드는 비용.

dp[i][j] = min(dp[i-1][j+1 % 3], dp[i-1][j+2%3]) + 해당 집을 idx j로 칠할 때의 비용)

즉, 현재 위치 직전의 집 중에서 현재 선택한 색깔을 제외한 나머지 색깔 중 최솟값 + 현재 위치에서 현재 색깔로 칠할 때의 비용을 계산한다.

 

이렇게 되면, dp[-1]에서 최솟값이 모든 집을 칠하는 비용의 최솟값이 된다.

 

 

 

	import sys
	n = int(sys.stdin.readline())
	arr = []
	for _ in range(n):
	arr.append(list(map(int, sys.stdin.readline().split())))
	table = [[0 for _ in range(3)] for _ in range(n)]
	for i in range(n):
	for j in range(3):
	if i == 0:
	table[i][j] = arr[i][j]
	else:
	table[i][j] = min(table[i-1][(j+1)%3], table[i-1][(j+2)%3]) + arr[i][j]
	print(min(table[-1]))

view raw [백준] RGB거리.py hosted with ❤ by GitHub