[백준] 1351번 : 무한수열

1351번: 무한 수열

1351번: 무한 수열

🤔 문제분석

다이나믹프로그래밍 + 깊이우선탐색으로 문제를 해결 할 수 있습니다.

깊이 우선탐색을 하게되면 P와 Q가 2이상이기때문에 지수시간이 됩니다. N이 10^12 이므로 O(N)으로는 문제를 해결 할 수 없습니다.

다이나믹 프로그래밍을 처음에는 배열을 N크기만큼 생성했었는데 N의 크기만큼 생성하지않고 딕셔너리 자료구조를 활용하였습니다. 딕셔너리 자료구조도 마찬가지로 메모리 크기가 지수의 크기만큼 생성되기때문에 훨씬 효율적입니다.

💻 코드

import sys
from collections import defaultdict

input = sys.stdin.readline
N, P, Q = map(int, input().split())
dp = defaultdict(int)

def A(num):
    if num == 0:
        dp.setdefault(num, 1)
        return 1
    
    if num in dp:
        return dp[num]
    
    left = num // P
    right = num // Q
    
    dp.setdefault(num, A(left) + A(right))
    
    return dp[num]

print(A(N))

🎯 피드백 및 개선사항

처음에는 배열을 사용하여 문제를 해결하려고 했는데 메모리가 자꾸 터지는겁니다 😢 그래서 무슨 방법이 있을까해서 탐색을 하는 과정이 지수시간임으로 메모리도 지수시간만큼만 필요하다는것을 깨닫았습니다. 배열이 엄청나게 큰 수가 필요할경우 다음에는 어떻게 풀어야할지도 고민해봐야 될 것 같습니다.