[Python] 1351번 : 무한 수열

 

문제 3줄 요약

 

1. A0 = 1

2. i 번째 값 = ⌊i/P⌋ 번째 값 + ⌊i/Q⌋ 번째 값

3. ⌊ x ⌋ = x를 넘지 않는 가장 큰 정수

 

 

 

 

⌊ ⌋ 가 오타인가 싶었지만,

아래 힌트를 보니 위의 설명과 같은 기호였다.

 

위의 기호는 

i/P 와 같은 나눗셈에서는 소수점을 지운 값

즉, 몫에 해당한다.

 

따라서

피보나치 함수에서 사용했던 상향식과 메모리얼을 이용하여

값을 구해주었다.

 

from sys import stdin

# 상향 접근 + 메모리얼
def func(num):
    if num == 0:
        return 1
    else:
        if num//P not in num_dict:
            num_dict[num//P] = func(num//P)

        if num//Q not in num_dict:
            num_dict[num//Q] = func(num//Q)

        return num_dict[num//P] + num_dict[num//Q]

if __name__ == "__main__":
    N, P, Q = map(int, stdin.readline().split())

	# 메모리얼 기능을 해줄 딕셔너리
    num_dict = {}
    print(func(N))

 

끝!