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

필요한 지식

1. 분할정복을 이용한 거듭제곱

접근

• i번째 징검다리 까지 가는 방법이 2^(n-2)가지가 나온다는 것을 찾는다.

• i가 1,2 인경우는 예외처리 해주고 나머지 경우는 2^(n-2)를 구해 출력한다.

• n의 범위가 10억 까지 이므로 거듭제곱을 구해줄 때 분할정복을 이용하여 O(log n)으로 빠르게 구해준다.

코드(C++)

#include <iostream>
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll go(int n) {
	if (n == 1) return 2;
	ll tmp = go(n / 2);
	if (n % 2) return (tmp * tmp * 2) % MOD;
	return (tmp * tmp) % MOD;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		ll n; cin >> n;
		if (n == 1 || n == 2)cout << "1" << "\n";
		else cout << go(n - 2) << "\n";
	}
	return 0;
}

결과