🧩 알고리즘
[백준] 2579 계단 오르기 - Python
yeonDev
2022. 2. 22. 11:24
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
POINT
Dynamic Programing (다이나믹 프로그래밍, dp)
피보나치 수열이 대표적인 예시이다. 1. 큰 문제를 작게 나눌 수 있고, 2. 작은 문제에서 구한 결과가 큰 문제에서도 사용되면 Dynamic Programing을 사용한다. 재귀(Top-down), 반복(Bottom-up) 두 가지 방법이 있으며, 시간 복잡도를 고려해서 반복문을 사용한다.
풀이
n = int(input()) # 계단 개수
scores = [0] * (n+1) # 계단 점수
for i in range(1, n+1):
scores[i] = int(input())
dp = [0] * (n+1)
dp[1] = scores[1] # 계단을 하나 오를 때 최댓값
dp[2] = scores[1] + scores[2] # 계단을 두 개 오를 때 최댓값
for i in range(3, n+1):
dp[i] = max(dp[i-3] + scores[i-1], dp[i-2]) + scores[i]
print(dp[n])