비요뜨의 징검다리 건너기 (18291번) - 백준 (BOJ)

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

18291번: 비요뜨의 징검다리 건너기

 

백준 - 비요뜨의 징검다리 건너기 (18291번)

 

난이도 : Gold 5

알고리즘 : Exponentiation By Squaring

Time Complexity : O( T * logN )

 

import sys
input = sys.stdin.readline


def get_rem(n: int) -> str:
    a = 2
    b = max(n-2, 0)
    ans = 1
    dnmnt = 1_000_000_007
    while b:
        a %= dnmnt
        if b&1:
            ans = ans * a % dnmnt
        a *= a
        b >>= 1
    return str(ans)


if __name__ == '__main__':
    print('\n'.join(get_rem(int(input())) for _ in range(int(input()))))

 

점화식

 

점화식을 세워보면,

1부터 N까지 가는 경우의 수는

1부터 N-1까지 가는 경우의 수의 2배라는 것을 알 수 있따.

 

즉, F(N) = 2 * F(N-1) 이다.

그리고 이를 일반식으로 표현하면

 

일반식 (n >= 2)

 

이렇게 된다.

 

---

일반식을 구했으니 이제 계산만 하면 된다.

 

하지만 숫자가 너무 크기 때문에,

중간중간 (10^7 + 9)로 나눠줘야 한다.

 

이를 실행하기 위한 방법이,

바로 거듭제곱의 거듭제곱을 활용하는 것이다.

 

n=23일 때의 예시

 

이진수의 성질을 활용해서,

log(N)의 속도로 빠르게 계산할 수 있다.