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

문제출처: https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

1. 코드

n = int(input())
 
stair = [0]
for _ in range(n):
    stair.append(int(input()))
 
if n ==1:
    print(stair[1])
else:
    dp = [0]*(n+1)
    dp[1]=stair[1]
    dp[2]=stair[1]+stair[2]
 
    for i in range(3, n+1):
        dp[i] = max(dp[i-3]+stair[i-1]+stair[i],dp[i-2]+stair[i])
    
    print(dp[n])

2. 해결과정

계단을 올라갈 때, 3칸 연속으로 올라갈 수 없고, 마지막 칸은 무조건 밟아야 한다.

1. dp[i] = dp[i-2] + arr[i]        -> i칸을 밟기 전의 칸이 i-2이므로 연속 밟지 않음

2. dp[i] = dp[i-3] + arr[i-1] + arr[i]  -> 한칸 전 dp가 아닌 3칸 전 dp로 이동 시킨 후 마지막 칸 더해줌

최종 점화식은 1과 2중 큰값이 되므로 dp[i] = max ( dp[i-2] + arr[i]   ,  dp[i-3] + arr[i-1] + arr[i] ) 가 된다.

 

3. 느낀점

dp어렵,,,진짜 어렵,,,