[Python] 백준 / silver / 2579 : 계단 오르기

문제 링크 : https://www.acmicpc.net/problem/2579

이번 달에는 dp 랑 백트래킹 문제만 파야겠다고 생각했다. 이 문제도 푸는데 꽤 오랫동안 고민했는데, 연속 3계단을 오를 수 없다는 제약 조건 때문이었다.

앞으로도 1차원 dp table 로 잘 안풀린다면, 2차원 dp table 을 고려해봐야겠다.
여기서 dp[i][0] = ( 전 계단을 밟지 않은 i 번째까지 계단의 최댓값 )
dp[i][1] = ( 전 계단을 밟은 i 번째까지 계단의 최댓값 ) 으로 설정했다.

정답을 맞추고 나서 다른 사람들은 어떻게 풀었나 살펴봤는데, 2차원 table 을 도입하지 않고도 풀 수 있는 문제긴 했다.

파이썬 코드

import sys
N = int(sys.stdin.readline())
stairs = []

for _ in range(N):
    stairs.append(int(sys.stdin.readline()))

if N == 1 or N == 2:
    print(sum(stairs))
else:
    dp = [[0]*2 for _ in range(N)]
    dp[0][0] = stairs[0]
    dp[0][1] = stairs[0]
    dp[1][0] = stairs[1]
    dp[1][1] = stairs[0] + stairs[1]

    for i in range(2, N):
        dp[i][0] = max(dp[i-2][0], dp[i-2][1]) + stairs[i]
        dp[i][1] = dp[i-1][0] + stairs[i]

    print(max(dp[-1]))