[파이썬/Python] 백준 2579번: 계단 오르기

📌 문제 : 백준 2579번

---

📌 문제 탐색하기

n : 계단의 개수 $(1 ≤ n ≤ 300)$
score : 각 계단의 점수 $(1 ≤ score ≤ 10,000)$

밟은 계단의 점수들을 모두 합해서 얻을 수 있는 점수 중 최댓값을 구하는 문제이다.

문제 풀이

⭐️ 계단 오르기 규칙

• 한 번에 한 계단씩 또는 두 계단씩
• 연속된 3개 계단 모두 밟으면 ❌
• 시작점은 계단에 포함 ❌
• 마지막 도착 계단 반드시 밟기

위의 규칙에 의해 계단을 오르는 방법이 2가지라는 것을 알 수 있다.
1️⃣ 한 계단만 오르기
2️⃣ 두 계단 오르기

2가지 방법으로 계단을 오르는 경우의 수를 구해 점수를 계산하고 그 중 최댓값을 찾아 출력하면 될 것이다.

경우의 수를 구하기 위해 DP를 활용한다.
계단 오르는 2가지 방법을 점화식으로 만들고,
n개의 계단을 다 오를 때까지 매순간 점수가 가장 높은 경우를 선택하다록 만들면 될 것 같다.
이 때, 연달아 3개의 계단을 모두 밟으면 안된다는 것을 유의해서 점화식을 만든다.

⭐️ 점화식 만들기

• 한 계단 올려와 현재의 계단 도달하기
  • 두 계단 밑까지 올라오는 방법까지의 최대 점수 + 현재 계단의 점수
• 두 계단 올라와 현재의 계단 도달하기
  • 세 계단 밑까지 올라오는 방법까지의 최대 점수 + 한 칸 밑 계단 점수 + 현재 계단
  • 연달아 3개의 계단을 모두 밟으면 안되기 때문❗️
• 초기값 계산 (n이 작을 경우에 대해 따로 정의)
  • n = 1일 때 한 계단만 오를 수 있음
    • 점수의 최댓값은 첫번째 계단의 점수
  • n = 2일 때 연달아 두 계단 오를 수 있음
    • 점수의 최댓값은 첫번째 계단의 점수 + 두번째 계단 점수
  • n = 3 인 경우부터 2가지 경우 다 이용 가능❗️

가능한 시간복잡도

DP 테이블 채우기 → $O(n)$

최종 시간복잡도
총 $O(n)$이 된다.
최악의 경우 $O(300)$이므로
이는 1초 내에 연산이 가능하다.

알고리즘 선택

DP로 최대 점수 구하기

DP 구현

1️⃣ dp 테이블를 정의한다.
2️⃣ dp 테이블의 초기값 계산한다.
3️⃣ 점화식에 따라 각 계단에 대한 dp 테이블을 채워준다.
4️⃣ dp 테이블의 마지막 값을 출력한다.

---

📌 코드 설계하기

1. 계단 수 입력
2. 계단 점수 입력
3. dp 테이블 정의
4. 점화식 초기값 채우기
5. dp 테이블 채우기
6. 결과 출력
   
   

---

📌 시도 회차 수정 사항

1회차

• n이 작은 경우를 따로 고려해주지 않았더니 n = 3이상의 dp 테이블을 채울 때 IndexError: list index out of range문제가 발생했다.
• if문으로 n에 따른 예외처리를 해주었다.

---

📌 정답 코드

import sys

input = sys.stdin.readline

# 계단 수 입력
n = int(input())

# 계단 점수 입력
scores = [int(input()) for _ in range(n)]

# dp 테이블 정의
dp = [0] * (n + 1)

if n == 1:
    print(scores[0])
elif n == 2:
    print(scores[0] + scores[1])
else:
    # dp 초기값 채우기
    dp[1] = scores[0]
    dp[2] = scores[0] + scores[1]

    # dp 값 채우기
    for i in range(3, n + 1):
        dp[i] = max(dp[i - 2] + scores[i - 1], dp[i - 3] + scores[i - 2] + scores[i - 1])

    print(dp[-1])

• 결과