백준 22.02.09. 2579번 - 계단 오르기

n = int(input())

step = [0 for i in range(300)]
dp = [0 for i in range(300)]

for i in range(n):
    step[i] = int(input())

dp[0], dp[1], dp[2] = step[0], step[0] + step[1], max(step[1] + step[2], step[0] + step[2])
for i in range(3, n):
    dp[i] = max(dp[i-3] + step[i-1] + step[i], dp[i-2] + step[i])

print(dp[n-1])

• 규칙을 찾는 것이 우선입니다.
• step에는 각 계단의 비용을, dp에는 각 계단까지의 최댓값을 저장합니다.
• 1번째, 2번째 계단의 최댓값은 step[0], step[0] + step[1]입니다.
• 하지만 2번째부터는 경우의 수가 나뉘기때문에 max메서드를 이용하여 경우의 수 중 최댓값을 저장해줍니다.
• 직접 할당해준 인덱스 이후의 값들은 두가지 경우의 수를 가집니다.
  • step[i]가 1. (연속되는 두번째 계단이 될 때) 와 2. (step[i]가 건너뛰고 시작되는 첫번째 계단일 때) 로 나뉩니다.
  • 따라서 step[i]가 1인 경우와 2인 경우의 값을 모두 구하여 최댓값을 구해주면 됩니다.
    • 만약 1번의 경우라면
      • step[i-2]를 건너뛰었기 때문에 dp[i-3] + step[i-1] + step[i]가 됩니다.
    • 만약 2번의 경우라면
      • step[i-1]을 건너뛴 상태이기 때문에 dp[i-2] + step[i]를 해주면 됩니다.
• 위 식을 반복실행하며 최댓값을 구하게 됩니다.