[백준/파이썬] 2579 계단 오르기

#문제링크

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

2579번: 계단 오르기

#나의풀이

import sys

if __name__ == '__main__':
    T = int(sys.stdin.readline())
    stair = [0]
    dp = [0] * (T+1)

    for _ in range(T):
        stair.append(int(sys.stdin.readline().rstrip()))

    if T == 1:
        print(stair[1])
    elif T == 2:
        print(stair[1]+stair[2])
    else:
        dp[1] = stair[1]
        dp[2] = stair[1] + stair[2]
        dp[3] = stair[3] + max(stair[1], stair[2])

        for i in range(4, T+1):
            dp[i] = stair[i] + max(dp[i-2], dp[i-3]+stair[i-1])
        print(dp[T])

#해설

문제를 읽는순간 DP라고 바로 생각이 들었던 문제 아래 계단부터 최대값을 구하고 위 계단을 구할때 아래 계단 값들을 이용 해야한다.

 

문제의 규칙을 보고 최대값을 구하려면 2가지 경우의 수가 나온다.

예를 들어 4번째 계단을 구한다고 할때 3개의 계단을 연속으로 밟을수 없으므로 1번째 계단의 최대값에서 3번째 계단을 밟고 4번째 계단으로 가는것과 2번째 계단의 최대값에서 바로 4번째로 가는것으로 나뉘어진다.

코드로 작성하게 되면 dp[i-3] + stair[i-1] 과 dp[i-2]의 max값을 구하고 stair[i]값을 더해주면 dp[i]가 나오게 된다.

 

백준에서 예외사항을 귀찮게 계단이 1개일때와 2개일때 설정해놓은거 같다 indexerror뜨는 경우는 저 2개에서 걸리게 된다.