[다이나믹 프로그래밍] ★★ 2749번 - 피보나치 수 3

[백준] 2749번 - 피보나치 수 3

(한줄평) 메모리 초과를 해결하지 못해 다른 사람의 풀이를 참고한 문제! 아예 생각조차 하지 못한 방식으로 해결이 가능하다... 답을 안봤으면 절대 못풀었을 문제^^;

유사 문제: 2747, 2748

https://hseungyeon.tistory.com/294

[다이나믹 프로그래밍] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2

이 문제는 n이 1,000,000,000,000,000,000이하의 자연수 일 때, n번째 피보나치 수를 1,000,000으로 나눈 나머지를 구하는 문제다.

(풀이1) 메모리 초과가 난 틀린 코드

풀이 시간: 20분 이내

1) 문제 해결 아이디어

첫번째 오류. 메모리 초과

일단 이 문제는 전에 풀었던 dp방식으로 코드를 돌리면 메모리 초과가 나는 문제가 있다. 

그도 그럴것이 n은 1,000,000,000,000,000,000이하의 자연수로 범위가 굉장히 커졌다.

그래서 dp 테이블(d)를 n의 크기만큼 만드는 것이 아니라 전전값, 전값, 현재값을 담을 변수 3가지를 사용했더니 메모리 초과가 나지 않았다.

 

두번째 오류. 시간 초과

위에서 변수 3가지를 설정했지만 이번엔 시간초과 문제가 생겼다. 여러가지 방법을 써봤지만 계속 되지 않아서 내가 모르는 무언가가 있을 것이라고 판단해 다른 사람의 풀이를 참고하기로 했다.

 

2) 소스코드

n = int(input())  # 10**18 이하의 자연수
d1, d2, d3 = 0, 1, 0
for i in range(n - 1) :
  d3 = (d2 + d1) % 1000000
  d1 = d2 % 1000000
  d2 = d3 % 1000000
print(d3)

(풀이2) 메모리 초과를 해결한 성공 코드

풀이 시간: 

1) 문제 해결 아이디어

이 문제는 n이 굉장히 크기 때문에 dp테이블에 값을 기록하며 풀 수 있는 문제가 아니다.

여기서는 피사노 주기라는 방법을 사용하여 문제를 해결 할 수 있다.

 

<피사노 주기란?>

피사노 주기는 피보나치 수를 K로 나눈 나머지는 항상 주기를 갖게된다는 원리다.

주기의 길이가 P일 때, N번째 피보나치 수를 M으로 나눈 나머지는 (N%P)번째 피보나치수를 M으로 나눈 나머지와 같다.

[참고] https://kyun2da.github.io/2020/08/30/fibonacci/

[백준/Python] 2749 피보나치 수 3 - Kyun2da Blog

[참고] https://getchan.github.io/algorithm/acmicpc_2749/

백준-2749-피보나치 수 3

2) 소스코드

n = int(input())  # 10**18 이하의 자연수
k = 10**6  # 피보나치 수를 나눌 값
# k = 10**n이면, p = 15*10**(n-1)
p = 15 * 10**5  # 피노사 주기

n %= p  # 우리가 구해야할 값
a, b = 0, 1  # 피보나치 수를 기록할 dp 테이블
for i in range(n - 1):
  a, b = b % k, (a + b) % k
print(b)