[백준] 1354: 무한 수열2 (Python)

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

import sys
N, P, Q, X, Y = map(int, sys.stdin.readline().split())

a = dict()
def an(i):
    if i<=0:
        return 1
    x, y = (i//P)-X, (i//Q)-Y
    if x not in a:
        a[x] = an(x)
    if y not in a:
        a[y] = an(y)

    return a[x]+a[y]

ans = an(N)
print(ans)

1) 아이디어

• 수열 $A_i = A_{⌊i/P⌋-X} + A_{⌊i/Q⌋-Y} (i≥1)$로 주어졌으므로 구하고자 하는 $A_i$를 두 부분으로 나누어 재귀호출한다.

• 중복되는 호출은 매번 새로 계산하지 않고, 최초 호출시에만 계산한 후 저장하여 재사용한다(메모이제이션).

2) 풀이

입력을 변수로 저장하고, 메모이제이션을 위한 딕셔너리 a를 선언한다.

정수 i를 인자로 받는 함수 an()을 정의한다.
i가 0보다 작거나 같은 경우에는 바로 1을 리턴한다.

if n<=0:
    return 1

조건에 해당하지 않는 경우 $⌊i/P⌋-X$를 x=(n//P)-X, $⌊i/Q⌋-Y$를 y=(n//Q)-Y로 선언한다.

x, y = (n//P)-X, (n//Q)-Y

x와 y가 딕셔너리 a에 키로 존재하는지 확인하고, 없는 경우에는 다음과 같이 재귀호출한다.

if x not in a:
    a[x] = an(x)
if y not in a:
    a[y] = an(y)

이제 a[x]와 a[y]의 값이 존재하므로 a[x]+a[y]를 반환한다.

3) 비슷한 문제

무한 수열 (골드5)
https://www.acmicpc.net/problem/1351