코드 # 1000000으로 나눈 값을 출력하라고 했으므로, 피사노 주기를 이용할 수 있다. def pisano(num): ans = 0 mod1, mod2 = 1,1 while 1: if ans == num-1: # ans의 값이 num-1에 해당할 때 탈출 break ans += 1 # 값 증가 mod1, mod2 = mod2, (mod1+mod2)%1000000 # 다음 값으로 넘어간다. return mod1 k = int(input()) findindex = k%1500000 # 주기는 1500000이므로, 나머지를 찾아서 계산해주면 된다. print(pisano(findindex)) 아이디어 1. 피사노 주기는 피보나치 수열을 임의의 수로 나누었을 때 그 나머지가 주기를 띄는 것을 말한다. 2. ..
피사노 주기
피사노 주기 피보나치 수열을 임의의 자연수 k로 나누었을 때, 그 나머지는 일정한 주기를 띄는데 이를 피사노 주기라고 한다. 코드 def pisano(num): # dp 테이블을 만들어서 하면 계산이 매우 느려진다. answer = 1 mod1, mod2 = 1,2 # 1,1은 종료조건인데, 시작 부분이기 때문에 1개 올리고 1,2부터 시작 while True: if mod1%num == 1 and mod2%num == 1: # 주기의 첫 부분인 1,1이 나오면 종료 break answer += 1 # 개수 1개 증가 # mod1에는 mod2를, mod2에는 그 다음 피보나치 수를 나눈 값을 할당 mod1, mod2 = mod2, (mod1+mod2)%num return answer tc = int(in..
