[백준/dp] 2579번: 계단 오르기 (실버3, python)

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

2579번: 계단 오르기

아이디어

N이 1이나 2일 경우를 제외한 계단 오르는 방법이 키워드이다.

• 1이나 2일 경우 아래와 같이 이동한 값이 항상 max 값이다. 
  
  

N > 2일 경우는 두 가지 경우의 수가 있다.

• 이전 칸에서 2칸 뛰어서 도착하는 경우
  • 이 경우 연속되는 칸을 밟을 일이 없으므로 dp[i-2] + stairs[i]를 하면 구할 수 있다.

• 이전 칸에서 1칸 뛰어서 도착하는 경우
  • 이 경우 연속되는 칸을 밟을 우려가 있기 때문에 dp[i-3] + stairs[i-1] + stairs[i]를 하면 구할 수 있다.

참고로 연속되는 칸을 밟은 것은 아래와 같은 상황을 말한다. (문제 조건에 명시되어 있다.)

전체 코드

N = int(input())

stairs = [int(input()) for _ in range(N)]
dp = [0] * N

if N <= 2: print(sum(stairs))
else:
    dp[0] = stairs[0]
    dp[1] = stairs[0] + stairs[1]
    for i in range(2, N):
        dp[i]=max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i])
    print(dp[-1])