[백준 12728] n제곱 계산 (python)

https://www.acmicpc.net/problem/12728

12728번: n제곱 계산

n제곱 계산 문제

(3+√5)를 n제곱 했을 때 소수점 앞 세 자리를 찾는 문제

분할 정복과 수학에 대한 이해가 있어야 풀 수 있었다.

⚙️내가 푼 정답코드

def mult(a,b): # 행렬의 곱 구하기
    A = [[0,0],[0,0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                A[i][j] += a[i][k]*b[k][j] % 1000 
    return A

def div(x,n): # 행렬을 n제곱 하기
    if n == 1:
        return x
    else :
        temp = div(x,n//2)
        if n % 2 == 0:
            return mult(temp,temp) 
        else:
            return mult(mult(temp,temp),x)

import sys
T = int(sys.stdin.readline())
for case in range(1,T+1):
    N = int(sys.stdin.readline())
    x = [[6,-4],[1,0]] # 점화식 행렬
    result = div(x,N)
    num = str((result[0][0] + result[1][1] -1)%1000) # 결과값값
    if len(num) == 3:
        print(f'Case #{case}: {num}')
    elif len(num) == 2:
        print(f'Case #{case}: 0{num}')
    elif len(num) == 1:
        print(f'Case #{case}: 00{num}')

📌 문제 접근 포인트

편의상 3+√5 = α, α^n+(4/α)^n = An라고 표현 
1. 주어진 문제가 3+√5의 n 제곱 임을 생각해보자. 이것을 단순하게 정말 n제곱 하면 1억이 넘는 n의 제곱이라 시간이 굉장히 오래걸리기도하고, 부동 소수점 때문에 정밀하게 구할 수가 없다.
2. 그럼 결국 소수점이 나오지 않는 정수를 이용해서 풀어야 한다는 뜻이다. 그럼 3+√5를 어떻게 정수로 만들어 줄 수 있을까?
3. 3+√5와 같이 자연수 + 무리수의 합을 없애려면, 켤레수에 대해서 생각해보면 된다. α와 α의 켤레수를 합하면 정수가 나오게 된다. 켤레수인 3-√5를 이용해보자.
4. 3-√5의 경우 (3-√5)(3+√5)/(3+√5) = 4/(3+√5)의 형태로 만들 수 있다. 즉 4/α이다 → 3번에 의해 α + 4/α의 형태를 구할 수 있다.
5. 우리는 α의 n제곱을 구해야하므로 똑같이 α의 n제곱 + α의 켤레수 n제곱근 = α^n + (4/α)^n임을 알 수 있다.
6. 그러면 α의 n+1제곱은 α^(n+1) + (4/α)^(n+1)이고, (α^n + (4/α)^n)*(α+4/α) - 4*(α^(n-1)+(4/α)^(n-1))로 표현 할 수 있다. 여기서 α+4/α = 6이므로 An+1 = 6*An - 4An-1의 점화식을 얻을 수 있다.
7. 점화식을 활용해서 행렬을 만들면 [[6, -4][0,1]]을 이용할 수 있다. 이 점을 활용하여 행렬의 제곱을 해주면 An의 일반 항을 구하도록 출력할 수 있다. 우리가 원하는건 끝에 3자리이므로 곱하는 과정에서 %1000을 통해 3자리만 남겨주자.
8. α를 구해보면 1부터 6, 28, 728 ... 이런식으로 바뀐다. 그럼 우리가 구한건 결국 An인데, 이걸 제곱으로 어떻게 활용하지? 생각할 수 있다. 여기서 α = 3+√5, 즉 5.xx의 형태, α^2 = 3+√5 = 27.xx의 형태로 나아간다. 우리가 구한 숫자는 해당 숫자를 올림한 형태의 정수 값임을 알 수 있다. 그러므로 최종 값에서 1씩 빼주면 얻을 수 있다.
9. 조건에 맞게 출력해주면 된다.