백준 2579번: 계단 오르기

백준 2579번: 계단 오르기

아이디어

계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있다. 이 문제의 까다로운 조건인 "계단 세 개를 연속해서 밟을 수 없다, 마지막 계단은 무조건 밟아야 한다" 를 만족시키려면 어떻게 해야 할까?

dp테이블에 해당하는 계단을 밟는 경우 그 이전 계단까지 포함해서 얻을 수 있는 최대한의 점수를 저장한다. 마지막 계단까지 dp테이블을 작성하면 자연스럽게 "마지막 계단은 무조건 밟아야 한다" 라는 조건을 만족시킬 수 있다.

첫 번째 계단까지 밟는 경우, 점수의 최댓값은 첫 번째 계단의 점수이다.
두 번째 계단까지 밟는 경우, 점수의 최댓값은 첫 번째 계단과 두 번째 계단 점수의 합이다.
세 번째 계단까지 밟는 경우, 점수의 최댓값은 첫 번째 계단과 세 번째 계단 점수의 합 / 두 번째 계단과 세 번째 계단 점수의 합 둘 중 더 큰 값이다.

dp[0] = stairList[0]
dp[1] = stairList[0] + stairList[1]
dp[2] = max(stairList[0], stairList[1]) + stairList[2]

네 번째 계단부터 일반화가 가능하다. N 번째 계단까지 밟았을 때 나올 수 있는 경우의 수는 두가지다.
case 1. N - 3 번째 계단까지 밟은 경우 점수의 합(dp[N - 3]) + N - 1 번째 계단의 점수 + N 번째 계단의 점수
case 2. N - 2 번째 계단까지 밟은 경우 점수의 합(dp[N - 2]) + N 번째 계단의 점수

dp[N] = max(dp[N - 3] + stairList[N - 1] + stairList[N], dp[N - 2] + stairList[N])

그림을 살펴보자.

case 1의 경우(파란색) N - 3번째 계단까지 밟은 경우가 dp테이블에 알아서 잘 저장이 되어 있을 것이다. 그림에서는 20 + 15 = 35가 저장되어 있을 것이다.
case 2의 경우(빨간색) N - 2번째 계단까지 밟은 경우가 dp테이블에 알아서 잘 저장이 되어 있을 것이다. 그림에서는 10 + 20 + 25 = 55가 저장되어 있을 것이다.
따라서 정답은 55 + 20 = 75가 된다.

이렇게 두 개의 case로 나누면 "계단 세 개를 연속해서 밟을 수 없다"는 조건을 만족시킬 수 있다.

코드

import sys
input = sys.stdin.readline

N = int(input())
stairList = [int(input()) for _ in range(N)]
dp = [0]*N

dp[0] = stairList[0]
if N > 1:
    dp[1] = stairList[0] + stairList[1]
if N > 2:
    dp[2] = max(stairList[0], stairList[1]) + stairList[2]
if N > 3:
    for i in range(3, N):
        dp[i] = max(dp[i - 3] + stairList[i - 1] + stairList[i], dp[i - 2] + stairList[i])

print(dp[N - 1])

여담

지금까지 풀었던 dp 문제중에 거의 제일 어려웠다... 이게 정보올림피아드 초등부 문제라고? 난 유치원생이 분명하다.