문제

무한 수열 A는 다음과 같다.

A0 = 1
Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)
N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력

첫째 줄에 AN을 출력한다.

제한

0 ≤ N ≤ 1012
2 ≤ P, Q ≤ 109

예제 입력 1

7 2 3

예제 출력 1

7

예제 입력 2

0 2 3

예제 출력 2

1

예제 입력 3

10000000 3 3

예제 출력 3

32768

예제 입력 4

256 2 4

예제 출력 4

89

예제 입력 5

1 1000000 1000000

예제 출력 5

2

풀이

안풀려서 풀이를 보고 싶게 만들었던 문제, 그러나 안보고 풀었다!
Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)
위 점화식을 보고, dp 라고 생각하여 bottom-up 으로 풀었고, 시간 초과 문제가 발생했다.

일반 bottom-up DP 풀이

import sys
import math
input = sys.stdin.readline

n, p, q = map(int, input().split())
dp = [1]

for i in range(1, n+1):
    f = math.floor(i/p)
    s = math.floor(i/q)

	dp.append(dp[math.floor(i/p)] + dp[math.floor(i/q)])

print(dp[n])

이를 해결하기 위해 인덱스 n 까지의 값을 구하는게 아니라, n//p 와 n//q 중에 큰 값까지의 dp 배열을 생성하여 dp[n//p] + dp[n//q] 를 출력하는 방식을 사용하여 시간 초과 문제를 해결하고 dp 배열의 메모리를 줄이고자 하였다.

연산 수와 메모리를 줄인 bottom-up DP 풀이

import sys
import math
input = sys.stdin.readline

n, p, q = map(int, input().split())
dp = {}
dp[0] = 1
v1, v2 = n//p, n//q
mv = max(v1, v2)
for i in range(1, mv+1): # bottom-up
    f = math.floor(i/p)
    s = math.floor(i/q)

    dp[i] = dp[f] + dp[s]

print(dp[v1] + dp[v2])

그러나 이번에는 시간 초과는 뜨지 않았으나, 메모리 초과가 발생하였다. dp 문제인데 dp 로 시간 초과가 발생하여 당황하였다. 그래서 top-down 방식을 생각해보았는데, 이 문제에서는 bottom-up 으로 차곡차곡 dp 배열을 생성해도 그 중에 사용하지 않는 값이 있다는 것을 알게되었고, 이럴 경우에는 top-down 방식을 사용하여 필요한 값만 저장하는게 메모리를 적게 사용한다는 것을 알게되었다!

예를 들어서, n 이 1000 인 경우에 bottom-up 방식을 사용하면 적어도 dp[1] ~ dp[500] 까지의 값들을 차곡차곡 쌓아올려야 하지만, top-down 방식을 사용하면 500, 250, 125, 62, ... 이런식으로 필요한 값만 구하고, 이를 기록하여 재사용 할 수 있게 된다.

여기서 주의할 점은, dp배열에 값을 기록하지 않고 그냥 사용한다면 dp 의 top-down 이 아니라, 단순 재귀이므로 시간초과가 발생한다.

일반적인 top-down DP 풀이

import sys
import math
input = sys.stdin.readline

n, p, q = map(int, input().split())
dp = {}
dp[0] = 1

def topDown(idx):
    if idx in dp:
        return dp[idx]
    v = topDown(idx//p) + topDown(idx//q)
    dp[idx] = v
    return v
res = topDown(n)
print(res)

알게된 점

같은 DP 라 하더라도, 동일한 문제를 풀때 bottom-up 과 top-down 의 연산 수, 메모리 사용량이 다를 수 있다는 것을 알게되었다.