[파이썬/python] 백준 - 1351 무한 수열

문제

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

---

문제 설명

1.   아래 조건을 만족하는 무한 수열 A가 존재한다.
   1. $A_{0} = 1$
   2. $ A_{i} $ =  $A_{\lfloor i/P \rfloor}$ + $A_{\lfloor i/Q \rfloor}$'
   3. $\lfloor x \rfloor$ = x를 넘지않는 가장 큰 정수이다.
      1. Ex) $\lfloor 3.5 \rfloor$ => 3

 

 

---

풀이

풀이 1

최초로는 단순 재귀를 통해 분할정복을 진행하다가 $A_0$이 등장했을 때 $A_0$의 값인 1을 리턴하도록 구현했지만, 시간초과가 발생했다.

1번 풀이로 진행했을 때 최악의 경우 $N = 10^{12}$, $P,Q = 2$일 때 트리의 구조는 각 분기마다 $2^i$회 만큼의 실행 횟수가 생기게 된다. $10^{12}$은 약$2^40$으로 치환이 가능하므로 $ 2^0 + 2^1 + 2^2 + ...... + 2^{39} + 2^{40} $의 실행횟수를 가지게 되고 가장 큰 상수로 시간복잡도를 계산하면 약 $O(2^{40})$ = $O(10^{12})$로 시간 제한인 2초를 훨씬 넘기게 된다.

 

풀이 2

풀이 1에서 생겼던 문제는 모든 i일 때 마다 값을 계산한다는 점이었다. 이 부분을 해결하기 위해 딕셔너리를 사용했다.

매 순간 연산을 할 때마다 현재 i에 해당하는 값이 딕셔너리에 존재한다면 다음 재귀로 가지 않고 바로 값을 리턴하고, 현재 i에 해당하는 값이 딕셔너리에 없다면 재귀를 통해 분할정복을 진행한다.

2번 풀이로 진행했을 때 최악의 경우 $N = 10^{12}$, $P,Q = 2$일 때 트리의 구조는 각 분기마다 1회의 실행 횟수가 생기게 되고 

n = $2^40$이기 때문에 약 $O(40)$의 시간복잡도를 가져 빠른 속도로 탐색을 하게된다.

1. 재귀를 통해 분할정복을 진행한다.
   1. 현재 n에 대해 연산한 적이 있다면 dic[n]을 리턴한다.
   2. 현재 n에 대해 아직 연산한 적이 없다면 딕셔너리에 recursion(n//p) + recursion(n//q) 값을 계산하여 저장한 후 dic[n]을 리턴한다.
2. 결과를 출력한다.

 

---

코드

import sys
input = sys.stdin.readline

n,p,q = map(int,input().split())

dic = {0:1}

def recursion(n):
    if n in dic:
        return dic[n]
    dic[n] = recursion(n//p) + recursion(n//q)
    return dic[n]

print(recursion(n))

---

시간복잡도

• 최악의 경우 $N = 10^{12}$, $P,Q = 2$ 일 때 약 $O(40)$의 시간복잡도를 가진다.