백준 무한 수열 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)을 구하는 문제이다.기본 수열 정의A(n)은 자기보다 작은 인덱스들의 결과를 이용해 계산됨 → 전형적인 DP 구조문제점N이 최대 10^12이기 때문에 일반적인 리스트 기반 DP(dp = [0]*(N+1))는 메모리 초과 → 딕셔너리 기반 메모이제이션 사용점화식 재귀 정의점화식에 따라 다음과 같이 재귀함수 작성A(n) = A(n // P - X) + A(n // Q - Y)기저 조건n 메모이제이션계산된 결과는 cache[n]에 저장해서 중복 호출 방지def dp(n): if n 재귀 함수를 정의한다.시간복잡도..