[구름LEVEL] 징검다리 건너기

문제

https://level.goorm.io/exam/49112/%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC-%EA%B1%B4%EB%84%88%EA%B8%B0/quiz/1

풀이

dp 를 활용한 풀이
점프 가능한 칸이 1~3 칸이므로
인덱스 3부터 순회하면서 이전 칸들중 가장 작은 값들과 더해가면서
최소 값을 저장해나간다.

N = int(input())
arr = list(map(int, input().split()))

def solution(N, arr):
	new_arr = arr + [0]
	dp = [0] * (N+1)
	dp[0] = arr[0]
	dp[1] = arr[1]
	dp[2] = arr[2]
	for i in range(3, N+1):
		dp[i] = new_arr[i] + min(dp[i-3], dp[i-2], dp[i-1])
	
	return dp[N]

print(solution(N,arr))