1. 문제 설명
https://www.acmicpc.net/problem/2749
2749번: 피보나치 수 3
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
2. 아이디어
내 방법이 너무 노가다가 심해서 다른 풀이를 찾아봤더니 피사노 주기라는 게 존재한다고 한다.
9471번: 피사노 주기
첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다.
www.acmicpc.net
하지만 코테 도중에 이렇게 모르는 개념 나온다고 서칭할 수 있는 것도 아니니 모르는 개념이 나왔을 때
해결할 수 있는 방법을 연구하는 것도 중요하다고 생각한다. (지금 알았으니 됐지!)
어쨌든 난 급하게 문제를 해결하기 위해 풀이했으므로 점화식으로 정리하고 말고 그런 건 없다.
DP로 O(N)까지 시간 복잡도를 줄여도 N이 1,000,000,000,000,000,000이라서 불가능하다.
이런 경우는 보통 패턴을 찾아서 해결해야 하는데, 피보나치 문제의 경우엔 대개 자릿수로 규칙성을 파악한다.
하지만 피보나치 수의 패턴은 이전에도 여럿 다루었는데 이 이상 더 뭘 해야할까?
이번에는 MOD 연산이 들어가므로 피보나치 수열의 모든 값들을 2부터 ~ 1,000,000까지 나누었을 때,
어떤 패턴이 나오지 않을까? 라고 가정해보고 시작한다.
다행히 반복하긴 한다. 그런데 사이클이 어떤 주기로 순회하는지 알아내기도 전에 벌써부터 값이 너무 커진다.
아무리 그래도 수기로 1,000,000은 커녕 10까지 하는 것조차 무리다.
그렇다. 수기로는 불가능하다. 그렇다면 코딩으로 값을 출력하면 된다.
import sys
input = sys.stdin.readline
def solution():
n = int(input())
MOD = 2
cache = [0, 1]
for i in range(2, 100):
cache.append((cache[i-1] + cache[i-2]) % MOD)
print(cache)
solution()
피보나치 수열을 만드는 프로그램을 만들고 MOD연산을 해준다.
테스트로 100번 째까지 MOD가 2인 경우로 결과를 확인해보니 내가 했던 결과가 일치한다.
그렇다면 이제 노가다로 찢으면 된다.
Cycle의 첫 시작은 무조건 0으로 시작하니까 0을 먼저 찾아서 그 뒤로 반복하는 지 확인한다.
MOD가 10인 경우는 주기가 60이다.
MOD가 2에서 주기가 3이었고, 10일 때 50이므로 100을 계산할 때는 주기가 꽤 클 것이다.
그렇다고 피보나치 수열 1부터 모두 출력하면 찾을 수 없다.
설령 패턴을 찾았더래도 인덱스를 어떻게 셀 수 있나.
여기서 조금만 더 머리를 굴려보자. MOD가 어떤 값을 가지던 간에 사이클의 시작은 무조건 0 1 1로 시작한다.
그렇다면 cache를 순회하면서 0 1 1의 패턴이 나올 때의 인덱스값을 출력하면 되는 것 아닌가?
flag, cnt = 0, 0
for idx in range(0, len(cache)):
if cache[idx] == 0:
flag = 1
continue
if flag == 1 and cache[idx] == 1:
cnt += 1
continue
if cnt == 2:
print(idx-3)
flag, cnt = 0, 0어차피 제출할 코드도 아니니까 깔끔할 필요도 없다. 이걸로 0 1 1이 나오는 모든 경우를 내게 보여줄 것이다.
MOD에 100을 넣어보고 돌려보자. print(cache)는 지우자. 이제 필요없으니.
주기가 300이다. 이대로 1000, 10000, 100000까지 넣어보자. (반복 횟수를 최대한 늘려준다.)
100부터는 패턴이 조금 달라져서 그 밑에 값에서는 구할 수가 없었다.
피사노 주기를 아는 사람이었다면 더 쉽게 풀 수 있었겠지만, 몰라도 포기하지 않으면 뭐든 풀 수 있다.
세상의 모든 수학공식과 알고리즘을 공부하고 테스트를 칠 수는 없지 않은가?
3. 코드
import sys
input = sys.stdin.readline
def solution():
n = int(input())
mod = 1000000
cycle = (mod // 10) * 15
cache = [0, 1]
for i in range(2, cycle):
cache.append((cache[i-1] + cache[i-2]) % mod)
print(cache[n%cycle])
solution()