백준 11444 풀이 (피보나치 수 6, 분할 정복, 행렬 제곱)

이 문제 정말 엄청난 삽질을 했다. 심지어 풀지도 못해서 풀이 찾아보니 아주 잘 정리한 식이 있었다. 그걸 사용하는 건가 보다. 이걸 사전지식 없이 어떻게 푼다는건지 정말 똑똑한 사람들......

처음 접근은 예전에 페르마의 소정리를 이용해서 풀려고 했다. 위키백과에 피보나치를 구하는 일반항이 존재했다. 생긴게 마치 예전에 풀었던 문제랑 비슷해서 비슷한 방식으로 2^n*5**0.5를 p-2승 해서 풀려고 했다.

그런데 문제가 루트때문인지 음수 제곱때문인지 자꾸 수가 망가져서 나누어 떨어지지도 않고 계산이 안되었다. 더구나 n승 만큼 제곱을 해주면 inf값이 나와서 계산이 안됐다.

 

그래서 삽질을 한참하다가 고수들 풀이를 구경갔더니 피사노 주기라는 키워드도 알게 되었고, 행렬제곱으로 피보나치를 구하는 일반항도 있다는 것을 알게 되었다.

굉장히 간단하다. 그냥 [[1,1][1,0]]을 제곱해주고 Fn을 구하면 끝이다. 물론 중간중간 1,000,000,007로 나머지만 구해주는 것을 잊지 않으면 된다.

이를 토대로 코드를 짜면 아래와 같다.

n = int(input())

s = [[1,1],[1,0]]
p = 1000000007

def power(n):
    if n == 1:
        return s
    ftmp = [[0,0],[0,0]]
    tmp = power(n//2)
    for i in range(2):
        for j in range(2):
            for _ in range(2):
                ftmp[i][j] += tmp[i][_]*tmp[_][j]
                ftmp[i][j] %= p
    if n%2 == 1: #홀수
        ftmp2 = [[0,0],[0,0]]
        for i in range(2):
            for j in range(2):
                for _ in range(2):
                    ftmp2[i][j] += ftmp[i][_]*s[_][j]
                    ftmp2[i][j] %= p
        return ftmp2
    else: #짝수
        return ftmp

tmp = power(n)
print(tmp[0][1])

이거 혼자 푼사람 천재 아닌가? 나의 무지에 다시 한번 반성하게 된다