백준 2749 python

문제 링크

문제 설명

문제 자체는 피보나치 수를 구하는 문제이지만 아이디어가 하나 필요했던 문제.

다른 피보나치 수 문제와 다르게 input의 숫자가 1,000,000,000,000,000,000 이하의 자연수라는 굉장히 어마어마한 바운더리를 가지고 있고, output의 조건은 input번째 피보나치 수를 1,000,000으로 나눈 것을 구하는 문제였다.

대단하다... 라는 생각을 가지면서 저 문제를 어떻게 풀면 좋을까를 곰곰히 고민해보다가 n이 충분히 큰 수이고, output으로 나오는 숫자가 1,000,000 이하의 수이기 때문에 때 연속된 피보나치수를 묶어보다보면 어느 타이밍에 수열이 반복되겠다라는 아이디어를 가지고 테스트해봤다.

n = int(input())
print(n)
m = 0
tmp1 = 1
tmp2 = 0
xxx = set()
while n != 1:
    
    tmp1,tmp2 = (tmp1+tmp2)%1000000,tmp1
    if (tmp1,tmp2) in xxx:
        print(m) # == 1500000
        print(tmp1,tmp2) # == 1 1
        break
    
    xxx.add((tmp1,tmp2))
    
    n -= 1
    m += 1
    
print(tmp1)

코드를 짜다가 그냥 즉석에서 넣은건데 이게 test코드로 가장 적당해보여서 따로 수정하지 않고 집어넣었다.

그 결과 주석으로 써져있는 것처럼 1,500,000번째에서 1,000,000으로 나눈 피보나치 수가 1,1이 들어감으로써 반복이 일어나는 것을 확인할 수 있었고 간단히 정답을 작성할 수 있었다.

정답코드

n = int(input())%1500000 # 1500000에서 1,2번째 피보나치 수가 반복됨. 

tmp1 = 1
tmp2 = 0
while n != 1:
    
    tmp1,tmp2 = (tmp1+tmp2)%1000000,tmp1
    
    n -= 1
    
print(tmp1)

cf. 쓰고 있는 글이 완성이 안되었는데 워낙 그 글을 올리고 싶었지만 시간의 이슈로 인해,,,,
그렇다고 1D1P 스터디의 마지막으로 실버문제는 올리기 싫어서 그래도 난이도가 조금 있다고 할 수 있는(?) 골드2 문제로 마무리를 해본다.