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

18291번: 비요뜨의 징검다리 건너기 (acmicpc.net)

 

접근 방법

도저히 감이 안잡혀서 점근식으로 접근해보았다.

 

N=3 인 경우

2
1 1

 

N=4 인 경우

3
2 1
1 2
1 1 1

 

N=5 인 경우

4
3 1
1 3
2 1 1
1 2 1
1 1 2
2 2
1 1 1 1

 

2 -> 4 -> 8 -> ...

2의 제곱 형태로 나아간다고 생각하여

2의 N-2 승을 이용하니 맞았다.

 

더 자세한 설명은 아래 참고 블로그를 확인해보자.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

#define ll long long

using namespace std;

ll t, n;
ll mod = 1000000007;

void powFunc(ll a, ll b) {
	ll res = 1;
	while(b) {
		if (b % 2 != 0) {
			res *= a;
			res %= mod;
		}
		a *= a;
		a %= mod;

		b /= 2;
	}
	cout << res << "\n";
}

int main() {
	cin >> t;
	while (t--) {
		cin >> n;
		if (n == 1) {
			cout << "1\n";
		}
		else {
			powFunc(2, n - 2);
		}
		
	}
	
}

 

참고

백준 18291번: 비요뜨의 징검다리 건너기 (tistory.com)

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