백준 알고리즘 - 계단 오르기 (2579) [Python]

 문제

 

 

 문제 상황

 

- 계단을 오르며 한번에 1칸, 또는 2칸만 오를 수 있을 때 얻을 수 있는 최대 점수 계산 

 

 해결 전략

 

- 기본적으로 피보나치이고 점수의 최대값을 계산해야하므로 dp를 사용한다.

 

 코드

 

import sys
input = sys.stdin.readline
 
N = int(input())
# 각 계단의 점수
stairs = [int(input()) for _ in range(N)]
def stair(N, stairs):
    stairs = [0] + stairs
    if N == 1:
        return stairs[1]
    elif N == 2:
        return stairs[2]+stairs[1]
    elif N == 3:
        return stairs[3]+max(stairs[1],stairs[2])
    # i번째 계단을 밟았을 때 그 때까지의 최고 점수
    score = [0 for i in range(N+1)]
    score[1], score[2], score[3] = stairs[1], stairs[2]+stairs[1], stairs[3]+max(stairs[1],stairs[2])
    # 연속된 세개의 계단을 모두 밟아선 안된다
    for i in range(4, N+1):
        score[i] = max(stairs[i-1]+score[i-3],score[i-2]) + stairs[i]
    return score[-1]    
 
print(stair(N,stairs))

 

 

 해설

 

- 일반적인 피보나치와 달리 연속 세칸은 안된다는 조건 때문에 dp에 점화식이 필요하다. 연속 세칸이 안되므로 선택지 이전 두칸이 연속적으로 밟힐 수 없으므로 그 전칸이 밟히면 n-2는 밟힐수 없으므로 n-3에서 저장해 놓은 값을 불러와야하고, n-2를 밟고 n-1을 안밟으면 바로 n-2에 저장된 값을 불러오면 된다. 즉 n번 칸을 밟을 방법은 n-1에서 출발하거나 n-2에서 출발해야하는데 n-2에서 출발하면 한번에 2칸만 뛰어야하고 n-1을 밟을 땐 n-2를 밟으면 안된다. 양쪽다 조건이 붙는다.

 

 새로 학습한 것 & 실수 

 

- 처음에 N이 작을 경우에 대한 처리를 하지 않았다.

 

 

출처 - https://www.acmicpc.net/problem/2579