BOJ/백준-2579-python

문제

풀이

• 다이나믹 프로그래밍 문제이다.
• 계단을 오르는 데는 아래와 같은 규칙이 있다.
  1) 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
  2) 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
  3) 마지막 도착 계단은 반드시 밟아야 한다.

코드

# https://www.acmicpc.net/problem/2579
# boj, 2579: 계단 오르기, python3
import sys

input = sys.stdin.readline

def dp(n, staris):
    if n <= 2:
        return sum(stairs)
    # dp table 초기화
    d = [0] * 301
    d[0] = stairs[0]
    d[1] = stairs[0] + stairs[1]

    d[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2])

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

    return d[n-1]

if __name__ == '__main__':
    n = int(input())
    stairs = [int(input()) for _ in range(n)]

    print(dp(n, stairs))

결과

출처 & 깃허브

BOJ 2579
github