[백준 18291번] 비요뜨의 징검다리 건너기 (C++)

문제링크 : https://www.acmicpc.net/problem/18291

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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

#define MOD 1000000007

ll fun(ll x, ll y)
{
	if(y<=0) return 1;
	else if(y%2==0) //짝수
	{
		ll tmp = fun(x, y/2);
		return (tmp * tmp)%MOD;
	}
	else //홀수
	{
		ll tmp = fun(x, y/2);
		return (tmp * tmp * x)%MOD;
	}
}

int main() 
{
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
   
	int T;
	cin >> T;
    while(T--)
    {
		ll N;
		cin >> N;
		cout << fun(2, N-2) <<"\n";
    }

   return 0;
}

N의 범위가 10억이기 때문에 분할정복을 이용한 거듭제곱을 이용하여 풀어야 한다.

 

만약 3^4 라고 가정하면 이는 (3^2)^2라고 할 수 있다.

만약 3^5 라고 가정하면 이는 (3^2)^2*3이라고 할 수 있다.

짝수일 때는 지수를 2로 나눠서 구한 것을 제곱하여 계산하고,

홀수일 때는 지수를 2로 나눈서 구한 것을 제곱하고 기존 값을 1번 곱하여 계산한다.

 

문제에 분할정복을 이용한 거듭제곱에 넣을 값을 또 구해주어야 한다.

 

N이 1일때 : 1

N이 2일때 : 1

N이 3일때 : 2

N이 4일때 : 4

N이 5일때 : 8

N이 6일때 : 16

 

이렇듯 N이 2일때부터 값이 2배씩 늘어나는 것을 볼 수 있다.

따라서 2^(N-2)임을 알 수 있다.