[Python] 2579번 계단 오르기

✏️ 문제

 

문제 파악

이 문제는 출발점을 기준으로 다음을 계산하는 거 보다 도착점을 기준으로 계산하는 게 더 편하게 풀 수 있다.

도착점을 기준으로 계산하기 위해 도착점으로 오는 경우는 생각하면 다음과 같다.

• 직전 칸에서 온 경우 (직전 칸을 밟은 경우 필히 3칸 전 칸을 꼭 밟음)
  • stair[n] + stair[n-1] + dp[n-3]
• 전전 칸에서 온 경우
  • stair[n] + dp[n-2]

이 두 경우 중 최대가 되는 값을 선택하면 된다.

이때 0 < n < 300 이므로 1과 2가 될 수 있는 경우도 생각해야 한다. 아니면 IndexError가 발생한다. (내 얘기)

 

알고리즘

• 다이나믹 프로그래밍 

 

 

코드

n = int(input())
stair = [0]

for _ in range(1, n+1):
  stair.append(int(input()))

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