[Python] 백준 / gold / 1351 : 무한 수열

문제 링크 : https://www.acmicpc.net/problem/1351

DFS + DP 문제. 문제는 간단하지만 메모리 이슈에 대해 고민해보기 좋은 문제였던거 같다. N 의 범위는 <= 10^12 이고, 메모리 제한은 128MB 이기 때문에 dp table 을 크기 N의 리스트로 잡으면 메모리 초과가 난다.

처음엔 for 문으로 i = 1~N 을 순회하면서 dp table 에 삽입했더니 메모리 초과가 났다. 그래서 dp table 을 리스트가 아닌 딕셔너리로 설정해줬다. 1~N 중에 값이 부여되지 않는 곳들이 있기 때문이다. dfs 를 진행하면서 dp 딕셔너리를 채워 넣었더니 정답처리를 받을 수 있었다.

메모리 측면에서 생각했을 때 리스트보다 딕셔너리가 효율이 좋은 경우가 있을 수 있다는 것을 기억해둬야 겠다.

파이썬 코드

from collections import defaultdict
import sys
N, P, Q = map(int, sys.stdin.readline().split())
dp = defaultdict(int)
dp[0] = 1


def dfs(x):
    if dp[x] != 0:
        return dp[x]
    else:
        dp[x] = dfs(x//P) + dfs(x//Q)
        return dp[x]


dfs(N)
print(dp[N])