[백준 / 2579] 계단 오르기

in Problem Solving on BaekJoon


날짜: 2022년 7월 12일
카테고리: 다이나믹 프로그래밍
태그: silver.3, 2579, 파이썬

백준 2579 - 계단 오르기

입출력 예시

예제 입력예제 출력
675
10 
20 
15 
25 
10 
20 

내가 적은 코드

import sys

N = int(sys.stdin.readline())
stair = list()
dp = list()

for i in range(N):
    stair.append(int(sys.stdin.readline()))

for j in range(N):
    if j == 0:
        dp.append(stair[0])
    elif j == 1:
        dp.append(max(stair[0] + stair[1], stair[1]))
    elif j == 2:
        dp.append(max(stair[0] + stair[2], stair[1] + stair[2]))
    # 첫번째 계단과 두번째 계단에서 나올 수 있는 경우를 미리 계산해 놓고
    # 다음 케이스의 -3번째 계단에서 다음 계단의 가중치가 최대가 되는 경우를 계산한다.
    else:
        dp.append(max(dp[j-3] + stair[j-1] + stair[j], dp[j-2] + stair[j]))
        # -3번째 계단에서 한칸씩 두번 올라갈 때 vs -2번째 계단에서 두칸을 올라갈 때
print(dp.pop())

풀이 과정

하노이의 탑 문제를 다이나믹 프로그래밍 예시로 보면서 풀다보니 DP에 대한 감이 잡혔다.
한번에 두 계단을 오를 수 있으니 두번째 계단까지에 나올 수 있는 경우의 수를 미리 계산해 놓고,
다음 케이스의 -3번째 계단에서 다음 계단의 가중치가 최대가 되는 경우를 계산하면서 쌓아나간다. 그리고 dp 배열의 마지막 원소를 pop()하면 된다.

베스트 코드

import sys
N = int(input())
li = [0 for i in range(301)]
dp = [0 for i in range(301)]
for i in range(1,N+1):
    li[i] = int(sys.stdin.readline())
dp[0] = 0
dp[1] = li[1]
dp[2] = li[1] + li[2]
for i in range(3, N+1):
    dp[i] = max(dp[i-2] + li[i], dp[i-3] + li[i] + li[i-1])
print(dp[N])

리뷰

  • 최대 계단 갯수가 300개라고 했으니 미리 300개의 원소가 들어있는 배열을 미리 생성해 놓고 반복을 돌려서 그런건지 로직은 나와 같은데 나보다 출력 시간이 빨랐다.
  • 거의 반년만에 다시 시작한 알고리즘인데 그래도 골드 하위까지는 풀만했었는데 이젠 실버3문제도 푸는데 오래걸렸다. 다시 감을 찾는게 중요할 듯…


© 2021. by hminkim