[골드 2] 백준 2749 - 피보나치 수 3 (파이썬)

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

풀이

이미지 출처 : https://velog.io/@cha-suyeon/python-피보나치-수열-만들기-점프투파이썬-종합문제-5번

피보나치 수열은 위 그림 처럼 제일 초기 1에서 1을 더한 값이 2, 2와 1을 더한 값이 3, …, n - 1번째 값과 n을 더한값.. 이런식으로 계속해서 늘어나는 수열이다.

결국 식을 작성하면 다음과 같다.

Fn = Fn-1 + Fn-2 (n >= 2)

이런식으로 n 이 17일때의 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다.

여기서 한가지 고려해야할 점은 시간 제한이 1초라는 것이다. 일반적인 제귀 방식으로는 시간초과가 날것이 뻔하다.

그래서 사용하는 것은 피사노 주기이다. (Pisano Period)

피사노 주기는 피보나치 수열을 어떤 수 M으로 나눈 나머지를 구할 때, 그 나머지들에서는 주기성이 생긴다.

여기서 주기성은 반복되는 패턴을 말한다. 이 반복되는 주기를 피사노 주기하고 한다.

예를 들어서 MOD = 3 일때 피사노주기는 다음과 같다.

N	fibo(N)	fibo(n) % 3
0	0	0
1	1	1
2	1	1
3	2	2
4	3	0
5	5	2
6	8	2
7	13	1
8	21	0
9	34	1
10	55	1
…	…	…

이 나머지들의 패턴은 어느 순간부터 다시 반복된다. 그래서 이 반복되는 길이가 피사노 주기이다.

핵심적으로 fibo(n) % M은 fibo(n % 주기) % M과 같다.

이걸 잘 활용하면, 엄청나게 큰 n도 주기만큼 줄여서 계산 할 수 있다.

이 문제에서는 MOD는 1,000,000이므로 피사노 주기는 1,500,000이다.

따라서 fibo(N) % 1000000 = fibo(n % 1500000) % 1000000 이다.

fibo = [0] * (n + 2)  # 0부터 n까지 계산하기 위해 n+2만큼 공간
fibo[1] = 1           # 초기값 설정 (fib(0) = 0, fib(1) = 1)

for i in range(2, n + 1):
    fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD  # 매번 MOD로 나머지만 저장

피보나치 수열을 반복문으로 구하는 코드이다.

이 과정은 단순한 반복문으로 피보나치 수를 누적하는 방식이다. n이 최대 1500000이므로, 시간이랑 메모리에 매우 효율적이다.

시간복잡도 분석

1. 시간 : O(Pisano) = O(1,500,000)
2. 공간 : O(Pisano) = 배열 하나만 사용

공간을 줄이는 방법을 생각하면 다음과 같다.

공간도 줄이고 싶다면 fibo[] 배열 없이 변수 2개로도 충분히 수정 할 수 있다.

a, b = 0, 1
for _ in range(n):
    a, b = b, (a + b) % MOD
print(a)

이건 공간 복잡도 O(1) 짜리 최적화 버전이다.

코드

# 백준 2749 - 피보나치 수 3

N = int(input())
MOD = 1000000

# # 시간초과 (1. 제귀 방식)
# def fibo(n : int) :
#     if n == 1 or n == 2 :
#         return 1
#     else :
#         return fibo(n - 1) + fibo(n - 2)

# print(fibo(N) % MOD)

# # 시간초과 (2. 이전값 + 전전값 더하는 방식)
# def fibo(n) :
#     a = 1
#     b = 1
#     if n == 1 or n == 2 :
#         return 1
#     for i in range(1, n) :
#         a, b = b, b + a
    
#     return a

# print(fibo(N) % MOD)

n = N % 1500000
fibo = [0] * (n + 2)
fibo[1] = 1

for i in range(2, n + 1) :
    fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD

print(fibo[n])