2579 계단 오르기 _python

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

2579번: 계단 오르기

계단을 두칸씩 오르면 무릎에 안좋다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

dp를 활용하는 문제.

0,1,2는 하드코딩을 해야한다.

이중 2는 이렇게 계산하면 된다.

시작에서 2칸을 바로 건너도 된다는 사실을 몰라서 이부분에서 오래걸렸다...

 

그 이후인 3부터는 1칸씩 반복계산하면 된다.

3부터 현재위치가 2칸건너 1칸으로 온 경우와 2칸만에 온 경우를 비교해야한다.

이부분도 상당히 시간을 잡아먹었는데, 2칸건너 1칸을 온 경우더라도 다음연산에 지장이 없다.

우측사진에서 보면 한칸만에 오던 두칸만에 오던, 2칸을 건넌다면 생각안해도 되니 파란색은 무시해도 된다.

빨간색만 생각하면 쉽게 풀린다.

이렇게 하면 마지막계단을 포함하면서 풀 수 있다.

 

문제 풀면서 쓴 주석

"""
2579 계단 오르기
1. 0,1,2에 대해 계산함
2. i번째가 2칸을 건너온곳인지 2칸후 1칸을 건너온곳인지 비교. -> N번 반복
"""

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline

"""
2579 계단 오르기
1. 0,1,2에 대해 계산함
2. i번째가 2칸을 건너온곳인지 2칸후 1칸을 건너온곳인지 비교. -> N번 반복
"""

#입력
N = int(input())
arr=[]
dp = []
for i in range(N):
    arr.append(int(input()))

if N>2:
    #하드코딩 0, 1, 2
    dp.append(arr[0])
    dp.append(arr[0]+arr[1])
    dp.append(max(arr[0]+arr[2],arr[1]+arr[2]))

    #dp반복
    for i in range(3,N):
        dp.append(max(dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i]))

    #출력
    print(dp[-1])
else:
    print(sum(arr))

88ms

 

dp는 어렵다...