백준 2579 : 계단오르기 (Python)

본문 링크

import sys
input=sys.stdin.readline

N=int(input())
L=[0]*301

for i in range(N):
    L[i]=int(input())

dp=[0]*301
dp[0]=L[0]
dp[1]=L[0]+L[1]
dp[2]=max(L[1]+L[2] , L[0]+L[2])

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

📌 어떻게 접근할 것인가?

3가지 규칙이 있다.

• 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.

• 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

• 마지막 도착 계단은 반드시 밟아야 한다.

$DP$ 를 사용해 풀었다.
첫번째부터 네번째 계단을 올라가는 경우를 생각하자.

• $DP[1]=L[1]$
• $DP[2]=L[1]+L[2]$ ( 한번에 2칸올라가는것보다 1칸 2번올라가는게 더 크다)
• $DP[3]=L[1]+L[3]$ or $L[2]+L[3]$ (1칸올라가고 2칸올라가기 , 2칸올라가고 1칸올라가기)
• $DP[4]=L[1]+L[3]+L[4]$ or $L[1]+L[2]+L[4]$ (1칸-2칸-1칸 올라가기 , 1칸-1칸-2칸 올라가기)

이다. 이때 $DP[4]$ 를 잘보면

$DP[4]$ 는 $DP[1]+L[3]+L[4]$ 와 $DP[2]+L[4]$ 로 나타낼 수 있다.

따라서 $DP[i]=max( DP[i-3]+L[i-1]+L[i] , DP[i-2]+L[i])$ 라는 수식이 만들어진다.

✅ 코드에서 주의해야할 부분

• 1번째 계단부터 3번째 계단까지는 미리 $DP$ 배열에 넣어준다.
• 올라간 지점에서 생각해보면 -1번째 계단과 -2번째 계단에서만 이동가능하다.