[골드 5] 백준 1354 - 무한 수열 2 (파이썬)

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

풀이

A(0) = 1  
A(n) = A(n // P - X) + A(n // Q - Y)   (n > 0)

주어진 N에 대해서 A(N)을 구하는 문제이다.

1. 기본 수열 정의
   • A(n)은 자기보다 작은 인덱스들의 결과를 이용해 계산됨 → 전형적인 DP 구조
2. 문제점
   • N이 최대 10^12이기 때문에 일반적인 리스트 기반 DP(dp = [0]*(N+1))는 메모리 초과 → 딕셔너리 기반 메모이제이션 사용
3. 점화식 재귀 정의
   • 점화식에 따라 다음과 같이 재귀함수 작성

   A(n) = A(n // P - X) + A(n // Q - Y)
   

4. 기저 조건
   • n <= 0인 경우에는 항상 1 반환 (문제에서 정의됨)
5. 메모이제이션
   • 계산된 결과는 cache[n]에 저장해서 중복 호출 방지

def dp(n):
    if n <= 0:
        return 1
    if n in cache:
        return cache[n]
    ret = dp(n // P - X) + dp(n // Q - Y)
    cache[n] = ret
    return ret

재귀 함수를 정의한다.

시간복잡도 분석

최악의 경우 호출 횟수

중복 호출을 피하므로, n이 다른 값으로 나뉘는 모든 경우의 수만큼만 호출됨. 정확한 횟수는 P, Q, X, Y의 값에 따라 달라지지만, 실질적으로 중복 없이 적은 수의 재귀 호출만 발생함.

• 시간 복잡도→ 보통 O(log N) ~ O(N) 사이의 작은 값
• 거의 모든 값은 O(number of unique states)
• 공간 복잡도→ O(number of unique calls) = 수천 ~ 수십만 정도로 충분히 가능
• 딕셔너리 크기 = 계산에 참여하는 서로 다른 n의 개수

코드

# 백준 1354 - 무한 수열 2
# 분류 : 다이나믹 프로그래밍

import sys
sys.setrecursionlimit(10 ** 7)

N, P, Q, X, Y = map(int, input().split())

cache = {}
def dp(n) :
    if n <= 0 :
        return 1
    if n in cache :
        return cache[n]
    ret = dp(n / P - X) + dp(n / Q - Y)
    cache[n] = ret
    return ret

print(dp(N))

import sys
sys.setrecursionlimit(10 ** 7)

N, P, Q, X, Y = map(int, input().split())

cache = {}

def dp(n):
    if n <= 0:
        return 1
    if n in cache:
        return cache[n]
    
    # n // P - X 와 n // Q - Y 로 int 계산
    cache[n] = dp(n // P - X) + dp(n // Q - Y)
    return cache[n]

print(dp(N))