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

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

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

 

 

 

 

 

 

 

 

 

 

문제 접근

분할 정복

1~N까지의 징검다리중 X번째를 밟고 지나갈 수 있다.

 (1<=X<=N) 1번과 N번을 제외하고 나머지 징검다리는 모두 밟거나 밟지않는다는 2가지중 1개로 정해진다.

 

 N=2의 결과: 1 

N=3의 결과: 2 

N=4의 결과: 4 

N=5의 결과: 8 

N=a의 결과: 2**(a-2) 

 

2의 제곱을 구하는 문제인데, N의 범위가 10^9라서 분할 정복으로 제곱을 해야함.

https://portable-paper.tistory.com/entry/%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

분할 정복 알고리즘

 

 

 

 

 

 

 

 

 

 

 

코드

import sys
input = sys.stdin.readline

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

"""
D = 10**9+7
def sol(n):
    if n==1:
        return 2
    res = sol(n//2)
    if n%2:
        return (res*res*2)%D
    else:
        return(res*res)%D
    

T = int(input())
for t in range(T):
    N = int(input())
    if N<3:
        print(1)
        continue

    print(sol(N-2))

30616

48