[DP 알고리즘] 2579번 계단오르기 풀이(파이썬)

안녕하세요. Harry입니다.

 

본 포스팅의 목적은, 코딩테스트를 준비함에 있어 백준에 제시된 문제 풀이와 스스로 얻은 정보를 정리하고자 합니다.

그러므로 단순히 문제를 푸는 것이 중요한 것이 아니라, 문제를 통해 얻어가는 것이 있어야하기 때문에 접근 방식은 이전 기초 300제를 풀었을 때랑 동일합니다.

 

[접근 방식]

- 문제에서 요구하는 역량은 무엇인지?

- 알고 있어야하는 지식은 무엇인지? 에 기반하여 풀이하고자 합니다.

 

- 백준 문제 링크입니다. : https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

[풀이 아이디어]

- 계단 번호 = dp 리스트의 인덱스 번호로 일치하도록 dp 리스트 생성

- 특정 계단 번호까지 갔을 때 도달할 수 있는 최대값을 dp리스트에 저장할 것. 매 계단마다 재귀함수로 돌려서 최대값을 매번 계산하고 갱신하는 것은 시간초과 위험

- N번째 계단에서 최대값 = (N-2)번째 최대값 + N번째 계단값 vs (N-3)번째 최대값+ (N-1)번째 계단값 + N번째 계단값
- 무조건 마지막 계단은 밟아야하므로, 위치한 계단의 숫자는 무조건 더해야한다는 전제조건 고려

 

import sys
input = sys.stdin.readline
n = int(input())

#dp 리스트 생성. (인덱스 순서 = 계단 순서)
dp = [0]*(n)
stair = [int(input()) for i in range(n)]
if n >2:
    dp[0] = stair[0]
    dp[1] = stair[0]+stair[1]
    dp[2] = max(stair[0]+stair[2],stair[1]+stair[2])
    for i in range(3,len(stair)):
        dp[i] = max(dp[i-3]+stair[i-1]+stair[i],dp[i-2]+stair[i])
    print(dp[-1])
else:
    print(sum(stair))

감사합니다.