📌 [BOJ] 백준 2579 계단 오르기

📖 문제

📖 예제

📖 풀이

import sys
input = sys.stdin.readline

N = int(input())
stair = [0]
for _ in range(N):
  stair.append(int(input()))


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

점수의 최대 값을 구하기 위해서는 목표 지점의 계단을 오르기 위한 다음 두 가지 방법을 고려하면 된다.
예를 들어 연속된 계단 1, 2, 3, 4가 있다고 가정하며 타겟 지점은 4층이다.
1. 1층, 2층을 거쳐 4층으로 가는 방법이다. 즉, dp[i] = dp[i-3] + stair[i-2]
2. 1층, 3층을 거쳐 4층으로 가는 방법이다. 즉, dp[i] = dp[i-2]
두 경우 중 큰 값에 목표 지점의 점수 stair[i]를 더해주어 출력하면 된다.