[Python] BOJ(백준) 1149번 - RGB거리

1. 링크

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

1149번: RGB거리

2. 난이도(solved.ac 참고)

실버1

3. 풀이

	# https://www.acmicpc.net/problem/1149
	import sys
	input = sys.stdin.readline
	n = int(input())
	street = [list(map(int, input().split())) for _ in range(n)]
	dp = [[0, 0, 0] for _ in range(n)]
	dp[0] = street[0]
	for i in range(1, n):
	for j in range(len(street[i])):
	if j == 0:
	dp[i][j] = min(dp[i-1][-1], dp[i-1][1]) + street[i][j]
	elif j == len(street[i])-1:
	dp[i][j] = min(dp[i-1][j-1], dp[i-1][0]) + street[i][j]
	else:
	dp[i][j] = min(dp[i-1][j-1], dp[i-1][j+1]) + street[i][j]
	print(min(dp[-1]))

view raw RGB거리.py hosted with ❤ by GitHub

다이나믹 프로그래밍 문제다. DP 배열을 선언하고 첫 값은 input값으로 받은 street의 첫 열을 그대로 갖다 붙인다.

다음 열로 넘어갈 때 각 dp의 값은, 이전 열의 같은 행 값이 아닌 다른 행의 값들에 + 현재 위치한 인덱스의 street값을 더해준 것 중 더 작은 것을 넣어준다. 이 과정을 반복하고 가장 마지막 열의 가장 작은 값을 출력하면 된다.