[백준/Python] 무한 수열

 

+

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

 

---

먼저 저는 다이나믹 프로그래밍을 사용해야겠다고 생각했습니다

예를 들어 n=7, p=2, q=3이 나왔을 때

 

다이나믹 프로그래밍

- 재귀 함수 + 메모제이션을 이용(탑다운 방식)

- 반복문을 이용(보텀업 방식)

 

---

먼저 반복문을 이용하여 코드를 구현했습니다.

from sys import stdin

n, p, q = map(int, stdin.readline().split())

dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n+1):
    dp[i] = dp[i//p] + dp[i//q]
    
print(dp[n])

하지만 n이 최대 10의 12승이기 때문에 메모리 초과가 났습니다.

---

 

그래서 저는 메모리를 줄이기 위해 n//p와 n//q의 max값까지만 메모리를 할당했습니다.

from sys import stdin

n, p, q = map(int, stdin.readline().split())

max_p = n // p
max_q = n // q
maxi = max(max_p, max_q)

dp = [0] * (maxi+1)
dp[0] = 1
for i in range(1, maxi+1):
    dp[i] = dp[i//p] + dp[i//q]
    
print(dp[max_p] + dp[max_q])

하지만 똑같이 메모리 초과가 났습니다.

---

 

이 문제는 dp의 모든 값을 사용하지 않고, 몇 개의 값만 사용되기 때문에 모든 것을 저장할 필요 없이

재귀+메모제이션을 쓰면 메모리 문제가 해결 됩니다.

from sys import stdin

n, p, q = map(int, stdin.readline().split())

arr = {0:1}
def dp(n, p, q):
    if n in arr:
        return arr[n]
    
    arr[n] = dp(n//p, p, q) + dp(n//q, p, q)
    return arr[n]
    
print(dp(n,p,q))