백준 2579 | 계단 오르기 (동적 계획법)

문제 출처 : https://www.acmicpc.net/problem/2579

문제

• 계단오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.
• 각각의 계딴에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
• 규칙
  1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
  2. 연속으로 세 개의 계단을 모두 밟아서는 안된다. 단 시작점은 계단에 포함되지 않는다.
  3. 마지막 도착 계단은 반드시 밟아야 한다.
• 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램 작성

입력

• 계단의 개수 : 300 이하의 자연수
• 계단에 쓰여 있는 점수 : 10,000 이하의 자연수

출력

• 이 게임에서 얻을 수 있는 총 점수의 최댓값 출력

문제 접근 방법

• 동적 계획법 문제는 부분 문제의 해를 이용하여 최종 문제의 답을 찾아가야 한다.

• 이 문제에서는 마지막 계단을 밟았을 때 의 점수의 최댓값 을 출력하는 문제였다.

  • 그렇다면 메모이제이션에 사용되는 dp 테이블 의 값으로는 점수의 최댓값이 들어갈 수 있겠다 라는 생각을 해볼 수 있다.
  • 마지막 계단에서의 답을 어떻게 부분 해로 찾을 수 있을까?
    • 계단이 1 개 일 때, 2 개 일 때부터 bottom-up 방식으로 dp 테이블 을 마지막 계단까지 채워나갈 수 있겠다 라는 생각을 할 수 있다.

• 연속된 3개의 계단을 오를 수 없기 때문에,

  • k 번째 계단에 오를 수 있는 경우의 수는
    1. (k - 2) 번째 계단을 밟지 않고, (k - 1) 번째 계단을 밟아서, k번째 계단에 오는 경우
    2. (k - 2) 번째 계단을 밟고, (k - 1) 번째 계단을 밟지 않고, k번째 계단에 오는 경우
       가 있다.
  • 점화식은 아래와 같다.
  $\displaystyle\ dp[k] = max(dp[k-2] + W[k], dp[k-3] + W[k-1] + W[k])$
  • $W$ : 각 계단의 점수가 저장된 리스트
  • $dp[k-2] + W[k]$ : (k - 2) 번째 계단을 밟고, (k - 1) 번째 계단을 밟지 않고, k번째 계단에 오는 경우
  • $dp[k-3] + W[k-1] + W[k]$ : (k - 2) 번째 계단을 밟지 않고, (k - 1) 번째 계단을 밟아서, k번째 계단에 오는 경우

코드

import sys

input = sys.stdin.readline
N = int(input())
W = [0]
for _ in range(N):
    W.append(int(input()))

dp = [0] * (N + 3)

# N == 1 edge case 
if N == 1:
    print(W[1])
    sys.exit()

# 기저 사례 
dp[1] = W[1]
dp[2] = W[1] + W[2]

# 점화식 (연속 3칸 점프 안됨)
for i in range(3, N + 1):
    dp[i] = max(
        dp[i - 2] + W[i],
        dp[i - 3] + W[i - 1] + W[i]
    )

print(dp[N])