피보나치수 6 파이썬

문제의 첫인상
1. N번째 피보나치수를 맞추는 문제
2. 1,000,000,007은 소수다
2-1. 굳이 소수를 준것은 페르마의 소정리를 이용하라는 뜻인가?
3. N의 범위가 매우크다(0~100경)동적계획법을 쓴다면 메모리 초과가 날것같은 그정도의 크기이다

조심스러운 접근

1. 피보나치수를 다구한다음에 나머지를 구하는 방법같은경우 피보나치수가 너무 커지기때문에 불가능하다고 판단
1-1. 피보나치수는 전수와 전전수를 더해서 만들어진다 만약 전수와 전전수 모두 나머지값들이면 서로 더한뒤 다시 나머지를 구해주면된다, 하지만 이방법역시 N이 매우 큰수이기때문에 계산도중 시간초과가 날것같았다

 

인터넷에서 해결책을 찾아보자

이문제가 행렬곱으로 푼다는사실은 문제설명에도 나와있어서 알고있었다

기존에 알고있던 방법으로 풀수있는방법은 많이 떠올랐지만 100경번째 피보나치수를 시간초과없이 알아내기에는 불가능해보였다

그래서 행렬곱을 이용한 풀이법에대해 고민해보았지만 아무리 고민해봐도 행렬곱을 이용한 해결책을 떠올리진못했다

관련포스팅을 여러개 읽어보앗지만 이해하는것조차 힘들었다 하지만 이곳의 글을 보고 이해하는것에 성공했다

https://johngrib.github.io/wiki/fibonacci/

피보나치 수열

 

---

 

피보나치수를 행렬제곱의 형태로 바꾸는것에 성공했으니 나머지는 바로 구현할수있을것이다

모듈러 연산을 활용한 행렬곱, 제곱구하는법은 전문제로 익숙해져있어 코드로 구현하는데 많은 어려움이 있지는 않았던것같다

 

느낀점

이번문제를 풀며 피보나치수를 행렬을 이용해 구하는법에대해 배워보았다

 

코드

# 피보나치 수 6
p=1000000007
N=int(input()) # 입력받기
d={}

def metrix_multiply(metrix1, metrix2,r1,c2,m,p): # 행렬곱과 나머지계산을 동시에 실행하는 함수이다, 행렬의 형태는 이중 리스트이다
    metrix=[]
    for i in range(r1):
        array=[]
        for j in range(c2):
            sumed=0
            for k in range(m):
                sumed+=metrix1[i][k]*metrix2[k][j]
            sumed=sumed%p
            array.append(sumed)
        metrix.append(array)
    return metrix

# 모듈러계산을 활용한 행렬 1110의 n제곱 % p 구현하기
def split_metrix(metrix,N): # 메모이제이션 적용
    try:
        return d[N]
    except:
        if N>1:
            splited=N//2
            d[N]= metrix_multiply( split_metrix(a,splited) , split_metrix(a,N-splited), 2,2,2,p) # 모듈러 연산의 구현
            return d[N]
        else:
            d[N]=metrix
            return d[N]

# 행렬의 제곱 계산
a=[[1,1],[1,0]]          
cal=split_metrix(a,N)

# 답안 도출
result=metrix_multiply(cal,[[1],[0]],2,1,2,p)
print(result[1][0])