[백준] 1351-무한수열

문제바로가기

최종 코드를 보여주기 전에 이렇게하면 메모리초과나 시간초과남 코드를 선보이겠다.

import sys
sys.setrecursionlimit(10**6)

N, P, Q = map(int, input().split())
def numbers(n):
    if n == 0:
        return 1
    return numbers(n//P) + numbers(n//Q)
    
print(numbers(N))

먼저 위 코드는 간단하지만 numbers를 중복해서 호출한다. N이 10^12이기 때문에 얼마나 많이 호출될지 안봐도 비디오.

N, P, Q = map(int, input().split())
a = [0]*(N+1)

def numbers(n):
    if n == 0:
        return 1
    if a[n] != 0:
        return a[n]
    a[n] = numbers(n//P) + numbers(n//Q)
    return a[n]

print(numbers(N))

다음으로 위 코드는 중복호출을 막기 위해 배열에 값을 저장해두는 코드인데, N이 10^12 내 범위의 매우 큰 수 이기 때문에 배열만으로 메모리 초과가 난다. (1TB 이상.. ^^)

import sys
sys.setrecursionlimit(10**6)

N, P, Q = map(int, input().split())
# a = [0]*(N+1)
a = dict()
def numbers(n):
    if n == 0:
        return 1
    if n in a:
        return a[n]
    a[n] = numbers(n//P) + numbers(n//Q)
    return a[n]

print(numbers(N))

결국 최종 코드는 딕셔너리를 이용하는 것. 필요한 만큼 가변적으로 크기가 변화하는 동시에 중복호출이 되지 않는다.

아 코테의 이 디테일함.. 어렵다