[파이썬/백준 2579번] 계단오르기

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

 

동적계획법,,

아 알았다! 싶으면 또 아니고 ...

아직까지 여러 유형을 공부한다고 생각하고 해야되는데

너무 어렵다 ㅜㅜ..

 

결국 다른 분 풀이 보고 했는데,

"합" 이라는 말에 계속 점화식을 찾으면서 

어떤 최댓값을 더해서 해야할지 찾고 있었는데

아하하 최대값,,,max,,max로 찾으면 되는것을,,

 

N=int(input())
nl=[0 for _ in range(301)]
for i in range(N):
    nl[i]=int(input())
dp=[0 for _ in range(301)]
dp[0]=nl[0]
dp[1]=nl[0]+nl[1]
dp[2]=max(nl[0]+nl[2],nl[1]+nl[2])

for i in range(3,N):
    dp[i]=max(dp[i-2]+nl[i],dp[i-3]+nl[i]+nl[i-1])

print(dp[N-1])

 

 

다음에 비슷한 유형으로 나오면 절대 놓치지 말아야지.