BOJ 18291, 비요뜨의 징검다리 건너기
ProblemSolving ·이 문제는 고속 거듭 제곱 알고리즘을 이용한 문제입니다!
풀이
이름은 거창하지만 사실 별거 없습니다.
이 문제를 딱 봤을때 첫번째와 마지막은 꼭 밟고 나머지는 밟고 가냐 안밟고 가냐 이기때문에 2의 n-2제곱을 구하면 되는 굉장히 쉬운 문제로 얕잡아 봤습니다. 하지만 시간 초과가 났습니다. 거듭제곱을 그냥해서는 시간초과가 나기때문에 거듭제곱에서 시간을 줄여야했습니다. 이때 사용한 알고리즘이 고속 거듭 제곱 알고리즘 입니다.
코드를 보셔도 사실 아무것도 아닙니다. 2의 지수를 반씩 나눠가며 분할정복 느낌으로 값을 구해주시면 됩니다.
코드 보시죠~
#include<stdio.h>
typedef long long ll;
ll t,n;
ll power(ll x, ll y)
{
if (y == 0)
return 1;
ll val = power(x, y / 2);
if(y%2==1)
return (x * val * val)%1000000007;
if(y%2==0)
return (val * val)%1000000007;
}
int main()
{
scanf("%lld", &t);
while (t--)
{
scanf("%lld", &n);
if (n <= 2)
printf("1\n");
else
printf("%lld\n", power(2, n - 2)%1000000007);
}
return 0;
}