[Python] 백준2579 계단 오르기

05 Jan 2023 in Study on Algorithm

백준2579 계단 오르기 링크

문제

예제 입력

---

코드

import sys

n = int(input())
stairs = [0] * (n+1)
dp = [0] * (n+1)

for i in range(1, n+1) :
    stairs[i] = int(sys.stdin.readline())

dp[1] = stairs[1]

if n != 1 :
    dp[2] = stairs[1] + stairs[2]

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

print(dp[n])

설명

파이썬을 통해서 사용자로부터 입력받아 자료형 list을 사용하여 dp알고리즘으로 계단 오르기를 구현했습니다.

---

정리

import sys

n = int(input())
step = [ int(sys.stdin.readline()) for _ in range(n) ]

print(step)

ans = 0
def solve(idx, res, cnt) :
    global ans
    if cnt == 2 :
        return
    if idx <= 0 :
        if ans < res:
            ans = res
        return
    res += step[idx - 1]
    # 1칸
    solve(idx - 1, res, cnt + 1)
    # 2칸
    solve(idx - 2, res, 0)

# 6 0 0
solve(n, 0, 0)
print(ans)

처음에는 자료형 list를 사용하여 재귀함수로 구현했는데 시간 초과가 발생했습니다. dp알고리즘은 재사용으로 시간을 줄이는데 중요한 역할을 합니다.

---

결과