2579 - 계단 오르기

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

2579번: 계단 오르기

 

- 재귀 (메모이제이션)

 

import sys
input = sys.stdin.readline

def step(x):
    if x <= 0:
        return 0
    if x == 1:
        return a[1]

    if d[x] != 0:
        return d[x]
    
    d[x] = max(step(x-2), a[x-1] + step(x-3)) + a[x]
    return d[x]

d = [0] * 301
n = int(input())
a = [0]
for _ in range(n):
    a.append(int(input()))

print(step(n))

문제를 이해하고 일단 브루트 포스 방식으로 푸는 문제는 절대 아닌 것 같아서 그 쪽으로 구현하려는 생각은 안했다.

처음엔 Bottom-Up 방식으로 dp 점화식을 세우려고 했는데.. 생각보다 잘 안됐음

 

쨋든 문제 중에 마지막 계단은 항상 밟아야한다는 조건을 보고 생각해낸건 마지막 계단부터 아래로 내려가는 Top-Down 방식 재귀 구현!

 

지점을 밟는 두 가지의 케이스로 분리해서 최댓값을 찾고 반환하는 재귀 함수를 구현했다.

그대로 넣으면 시간 초과가 발생해서 d라는 리스트로 메모이제이션을 통해 극복햇당

 

 

탑다운으로 만들어보니 dp식이 그냥 나왔다

dp[1] = a[1]
dp[2] = a[1]+a[2]

dp[i] = max(dp[i-2], dp[i-3]+a[i-1]) + a[i]

 

탑다운으로 작정하고 풀어본건 처음이라 기분 좋당ㅋ

어떤 문제는 바텀업보다 탑다운이 더 쉬운 것 같다고 느꼈다

 

ps. 근데 이거 초등부 문제던데 초딩들은 이걸 어케 푸는건가...