[BOJ | 백준] 18291번: 비요뜨의 징검다리 건너기

by Kimcoding on 2020-02-26 20:36

in BOJ

문제 설명

BOJ 18291

1에서 출발하여 N에 도착하려고 할 때 중간에 있는 징검다리들을 선택해서 올라가는 경우의 수를 구하면 됩니다.

풀이

문제를 보면 1에서 출발하여 N에서 도착해야 하고

현재 위치한 징검다리 번호를 i라고 했을 때 다음갈 수 있는 징검다리 번호는 i+1~N입니다.

그 말은 1번과 N 번은 무조건 올라가야 하고 2~N-1의 징검다리는 올라가거나 지나치거나 할 수 있습니다.

예를 들어 2번을 올라가고 나머지를 지나치면 1 → 2 → N

2번을 지나치고 나머지도 지나치면 1 → N 이 됩니다.

그러므로 총 경우의 수는 2^(N-2) 입니다.

N이 최대 10억이니 O(N)으로 말고 분할 정복을 이용한 거듭제곱을 구하면 됩니다. O(lgN)

이 방법은 다 아실 것이라 생각하고 코드로 넘어가겠습니다.

모르시는 분들은

BOJ 1629

을 풀어보세요 :)

소스 코드

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mod ((int)1e9 + 7)
using namespace std;

int main() {
	FIO;
	auto pw = [&](int a, int b) {
		int ret = 1;
		while (b >= 1) {
			if (b & 1) ret = (1LL * ret * a) % mod;
			b >>= 1, a = (1LL * a * a) % mod;
		}
		return ret;
	};
	int t; cin >> t; while (t--) {
		int n; cin >> n;
		cout << pw(2,n-2) << '\n';
	}
	return 0;
}