BOJ 2749 (피보나치 수 3)

문제

난이도: 골드 2

첫 번째 시도

• 방식: Memoization
• 시간복잡도: O(N) (O(10 ^ 18))

피보나치를 구현할 때, 가장 먼저 접근해 볼 수 있는 방식입니다.

import sys

IN = sys.stdin.readline

N = int(IN())

fibonacci_map = [0, 1]

def fibonacci(i: int) -> int:
  if len(fibonacci_map) < i + 1:
    tmp = fibonacci(i - 2) + fibonacci(i - 1)
    if tmp >= 1000000:
      tmp %= 1000000
    fibonacci_map.append(tmp)

  return fibonacci_map[i]

print(fibonacci(N))

하지만 Recursion 에러가 발생했습니다.

백준 채점 서버에서 파이썬 코드를 채점할 때, 재귀의 최대 깊이가 1000으로 설정되어 있다고 합니다. (참고)

입력 가능한 최대값이 어떻게 읽어야 하는지 조차 모를 정도로 큰 값이기 때문에, 재귀를 사용하지 않고 푸는 방법을 찾아야 했습니다.

두 번째 시도

• 방식: Memoization
• 시간복잡도: O(N) (O(10 ^ 18))
• 특이사당: 재귀 제거

재귀를 사용하지 않기 위해서 리스트에 피보나치 값을 각각 하나씩 채우는 방법을 생각했습니다.

fibonacci_map [0]은 0번째 피보나치 수를 표현하는 것입니다.

import sys

IN = sys.stdin.readline

N = int(IN())

fibonacci_map = []

i = -1
while i < N:
  i += 1
  if i == 0:
    fibonacci_map.append(0)
    continue
  if i == 1:
    fibonacci_map.append(1)
    continue

  v = fibonacci_map[i - 2] + fibonacci_map[i - 1]

  if v >= 1000000:
    v %= 1000000
  fibonacci_map.append(v)

print(fibonacci_map[N])

이는 메모리 초과라는 결과를 가져왔습니다.

N의 최댓값이 무수히 크다 보니, 메모리가 fibonacci_map의 크기를 감당하지 못하는 것으로 보입니다.

세 번째 시도 (정답)

• 방식: 점화식 발견
• 시간 복잡도: O(log2(N))

여기서부터는 도저히 방법이 생각나지 않아서 검색을 시도했습니다.

이 블로그 그를 통해서 피보나치 수는 다음 점화식을 따른다는 점을 알 수 있었습니다.

피보나치 수에서 적용되는 점화식

위 수식을 기반으로 구현한 코드입니다.

import sys

IN = sys.stdin.readline

N = int(IN())

fibonacci_map = {
  0: 0,
  1: 1,
  2: 1,
  3: 2,
  4: 3,
}

def fibonacci(i: int) -> int:
  if i in fibonacci_map:
    return fibonacci_map[i]

  tmp = None
  if i % 2 == 0:  # 짝수
    tmp = fibonacci(i // 2) ** 2 + 2 * fibonacci(i // 2) * fibonacci(
        i // 2 - 1)
  else:  # 홀수
    tmp = fibonacci(i // 2 + 1) ** 2 + fibonacci(i // 2) ** 2

  if tmp >= 1000000:
    tmp %= 1000000

  fibonacci_map[i] = tmp

  return tmp

print(fibonacci(N))

세 번째 시도는 입력값이 압도적으로 클 경우, 제가 알지 못하는 점화식이나 공식이 존재한다는 점을 눈치채야 한다는 점을 깨달았습니다.

네 번째 시도 (정답)

• 방식: 피사노 주기

다른 풀이 방법을 찾다 보니 피사노 주기를 활용한 풀이가 많이 나왔습니다.

피보나치 수를 특정 숫자(M)로 나누면 주기가 발생한다는 것이 피사노 주기의 핵심입니다.

또한 특정 숫자 M이 10^n이라면 주기는 15 * 10^(n-1)이라고 합니다.

이를 통해 두번째 시도에서 사용한 코드에서 5번째 라인만 수정하여 해결할 수 있었습니다.

문제에서는 M = 1000000이었기 때문에 주기는 1500000입니다.

import sys

IN = sys.stdin.readline

N = int(IN()) % 1500000

fibonacci_map = []

i = -1
while i < N:
  i += 1
  if i == 0:
    fibonacci_map.append(0)
    continue
  if i == 1:
    fibonacci_map.append(1)
    continue

  v = fibonacci_map[i - 2] + fibonacci_map[i - 1]

  if v >= 1000000:
    v %= 1000000
  fibonacci_map.append(v)

print(fibonacci_map[N])

느낀 점

피사노 주기를 활용한 풀이를 공부하며 느낀 점은, 피사노 주기를 몰라도 풀 수 있도록 연습해야 한다는 점이었습니다.

• 무수히 큰 N의 최댓값
• 뜬금없는 1000000으로 나눈 나머지를 구해야 한다는 조건

어쩌면 문제는 주기가 존재한다고 알려주고 있는 듯합니다.

테스트를 통해 1000000으로 나누었을 때 어떠한 주기로 반복되는지 찾았어야 했을 것 같습니다.

 

2749번: 피보나치 수 3