[BOJ] 2579. 계단 오르기

📌 문제 제목

문제 링크: BOJ 2579

---

🗒️ 문제 설명

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.

각 계단에는 점수가 쓰여있고 그 계단을 밟으면 점수를 얻게 된다.

다음과 같이 도착점까지 간다면 10 + 20 + 25 + 20 = 75점을 얻게 된다.

계단을 오르는데는 다음과 같은 규칙이 있다.

• 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
• 연속된 세 개의 계단을 모두 밟아서는 안된다.
• 마지막 도착 계단은 반드시 밟아야 한다.

각 계단에 쓰여있는 점수가 주어질 때, 이 게임에서 얻을 수 있는 점수의 최댓값을 구하여라.

시간 제한: 1초

메모리 제한: 128MB

계단의 개수 <= 300

계단에 쓰여있는 각 점수 <= 10,000

---

💡 문제 해결 아이디어

• 마지막 계단을 무조건 밟아야 하므로 마지막 계단을 밟기 위해 그 전에 밟아야 하는 경우는 두 가지
  • dp[i] = stairs[i] + stairs[i-1] + dp[i-3]
  • dp[i] = stairs[i] + dp[i-2]
  • 왜냐, 연속된 세 개의 계단을 밟으면 안되니까.
• 테이블 정의
  • dp[i]는 i번째 계단까지 올라왔을 때의 최대 점수
• 점화식 찾기
  • dp[i] = max(stairs[i-1] + dp[i-3], dp[i-2]) + stairs[i]
• 초기값 정하기
  • dp[1] = stairs[1]
  • dp[2] = stairs[1] + stairs[2]
  • dp[3] = max(stairs[1], stairs[2]) + stairs[3]

---

⌛️ 시간 복잡도

• O(N)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

n = int(input().strip())
stairs = [0] + [int(input().strip()) for _ in range(n)]

dp = [0] * (n+1)

if n == 1:
    print(stairs[1])
elif n == 2:
    print(stairs[1] + stairs[2])
else:
    dp[1] = stairs[1]
    dp[2] = stairs[1] + stairs[2]

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

    print(dp[n])