백준 2579 파이썬 - 계단 오르기 - 동적 계획법

백준 2579 파이썬

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

2579번: 계단 오르기

이번 문제는 조건에 맞춰서 계단을 오르면서 최대값을 구하는 문제입니다.

• 계단은 한번에 1~2 계단씩 오를 수 있다.
• 시작점은 포함하지 않고... 연속된 3개의 계단은 밟을 수 없다. 즉, 최대 2개 계단까지 연속으로 밟을 수 있다.
• 마지막 계단에는 반듯이 도착해야한다.

동적 계획법을 사용하면 현재 위치의 최대값을 저장하면서 가기 때문에... 3번 째 조건은 크게 걱정할 것 없고... 문제는 3개의 연속된 계단을 밟을 수 없다는 조건을 구분하기 위한 방법입니다.

 

3번 연속 밟으면 안되기 때문에 2번 연속까지는 밟을 수 있다. 그러면... 현재 위치에 있는 계단은 2가지 조건이 생긴다.

• 이전에 2계단 연속으로 오르고 현재 계단이 2계단을 오른 곳
• 3계단 이전에서 2계단을 오르고 바로 이전 계단에서 부터 현재 계단까지 연속으로 오른다.

2가지 조건 중 최대값이 해당 위치의 최대값이다.

 

 

Python 풀이

import sys
read = sys.stdin.readline

n = int(read())
stairs = [0] + [int(read()) for _ in range(n)] + [0]
cache = [0] * (n+2)
cache[1] = stairs[1]
cache[2] = cache[1] + stairs[2]

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

• 각 계단 별 수치와 누적된 현재 위치의 최대값 모두 리스트로 사용된다.

누적되는 메모이제이션 캐시값 기준을 바로 이전 위치로 생각하면 많이 헷갈릴 수 있다. 이번 문제는 2,3 계단 전이 기준이된다.