코드

import sys

input = sys.stdin.readline

n = int(input())

def stair_up(n):
    
    # 누적 합을 더할 DP 테이블
    d = [0] * (n+1)

    score = [0] * (n+1)
    
    # 인덱스를 편의상 통일시키기 위해 범위를 아래와 같이 설정
    for i in range(1, n+1):
        score[i] = int(input())
    
    # 별도로 처리하지 않으면 IndexError 발생
    if n == 1:
        return score[1]    

    d[1] = score[1]
    d[2] = d[1] + score[2]

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

    return d[n]

print(stair_up(n))

문제 해설

동적 프로그래밍 참고

동적 프로그래밍 문제로 다른 동적 프로그래밍 문제들과 마찬가지로 점화식을 세워서 코드화 시키는 것이 가장 중요한 부분이다. 이 문제의 경우 문제의 조건으로 아래와 같이 주어졌다.

1. 맨 마지막 계단은 반드시 밟아야 함 2. 연속된 세 개의 계단을 밟을 수 없음 3. 한 번에 한 계단 또는 두 계단씩 오를 수 있음

문제의 접근 방향을 첫 계단부터 마지막까지 올라가는 방향으로 생각하는 것보다 1번 조건에 따라 마지막 계단은 무조건 밟아야 하므로 마지막 계단에서부터 아래로 내려가는 방향으로 생각하여 점화식을 세웠다.

즉, 마지막 계단을 N번째 계단이라고 할 때, 여기에 도달할 수 있는 경우는 아래 두 가지와 같다.

  1. N-2번째부터 한 번에 2계단을 올라온 경우

    • 이 경우, 마지막 전 계단을 밟지 않은 경우가 된다

    • 계단 위치 변화 : (N-2) -> n
    • 마지막 계단을 밟기 전의 누적 합 : d[N-2]

  2. N-3번째 전에 두 계단을 올라온 경우

    • 이 경우, 마지막 전 계단을 밟은 경우가 된다

    • 계단 위치 변화 : (N-3) -> (N-1) -> n
    • 마지막 계단을 밝기 전의 누적 합 : d[N-3] + score[N-1]

위 두 경우 중 값이 더 큰 값이 정답이 된다.

댓글남기기

참고