백준 2579번(계단 오르기) 파이썬

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

2579번: 계단 오르기

계단 오르기 문제이다. 가장 대표적인 DP 문제중 하나라고 할 수 있다.

DP 유형은 코딩테스트 단골 유형이므로 반드시 익히고 가야하는 유형 중 하나이다.

오늘 이 DP 문제를 풀어보도록 하겠다.

 

import sys
input = sys.stdin.readline

num = int(input())
dp=[0]*(num+3)
d=[0]*(num+3)

for i in range (1,num+1):
    d[i]=int(input())

dp[1]=d[1]
dp[2]=d[1]+d[2]
dp[3]=max(d[3]+d[2],d[1]+d[3])
    

for j in range(4,num+1):
    dp[j]=max(dp[j-3]+d[j]+d[j-1],dp[j-2]+d[j])

print(dp[num])

이 문제는 DP의 대표적인 문제여서 그렇게 크게 어렵진 않았다.

하지만 DP가 뭔지 모르는 상태에서 푼다면 풀 수 없을것이다.

DP나 다른 고난이도 유형의 문제를 풀때는 유형에 대한 공부를 먼저 해야 한다고 생각한다.