백준 2579 : 계단 오르기

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

해결 방법 : 다이나믹 프로그래밍

• 기본적인 DP문제이지만, 계단을  3개 연속으로 밟을 수 없다는 조건만 고려해주면 된다.
• 연속으로 밟아진 경우를 따로 고려하지 않아도 되도록 점화식 자체에 n-1번째 DP테이블 값을 참조하지 않고, n-2, n-3번째 DP테이블 값을 사용한다.
• 점화식 : dp[n] = max(dp[n-2] + stairs[n], dp[n-3] + stairs[n-1] + stairs[n])

 

import sys
input = sys.stdin.readline

def solution(n, stairs):
    if n == 1: return stairs[0]

    d = [0 for i in range(n + 1)] # DP 테이블
    d[0], d[1], d[2] = 0, stairs[0], stairs[0] + stairs[1] # 초기값

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

    return d[n]

if __name__ == '__main__':
    n = int(input())
    stairs = []
    for i in range(n):
        stairs.append(int(input()))
    result = solution(n, stairs)
    print(result)