[구름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

풀이

[구름LEVEL] 징검다리 건너기 (난이도 3)

• [알고리즘 : DP(동적 계획법)] 🔥

<✅ 문제 요약>
0. 용민이가 독극물이 최대한 묻지 않도록 걷너뛰며 돌을 밟았다고 가정했을때,
1. 용민이에게 묻는 독극물의 양은 얼마인가?
2. 최대 3칸씩 건너뛸 수 있다.

<✅ 풀이방법>

0. 이전 인덱스 확인하고 세개중에 작은거 더해주면 끝

코드(code)

import sys
input = sys.stdin.readline

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

dp = [0]*N
# 최대 3칸 뛸 수 있으므로 3개까지는 가능하다.
dp[0]=stones[0]
dp[1]=stones[1]
dp[2]=stones[2]
# 이전 인덱스 확인하고 세개중에 작은거 더해주면 끝
for i in range(3,N):
	dp[i]=stones[i] + min(dp[i-1],dp[i-2],dp[i-3])

print(min(dp[len(dp)-1],dp[len(dp)-2],dp[len(dp)-3]))

회고

• DP인 근거는 해당 문제는 결국 이전의 금액들을 비교하면서 앞의 값을 여러 번 구한다는점에 있었다.

• [해당 코드]

  https://github.com/joejames0830/ps_study/blob/main/DP/%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC.py