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

\(DP[N] : N\)번째 징검다리를 건널때 나올 수 있는 경우의 수 라고 잡아보면

\(DP[N] = DP[N-1]+DP[N-2]+...+DP[1]\) 이라는 식이 나오는데

\(DP[N-1] = DP[N-2]+DP[N-3]+...+DP[1]\)

\(DP[N-2] = DP[N-3]+DP[N-4]+...+DP[1]\)

                         .

                         .

                         .

 

\(DP[1] = 1\)

이제 \(DP[1]\) 부터 \(DP[n-1]\)을 \(DP[n]\) 의 식에 대입해 보면

\(DP[N] = 2^{1}(DP[N-2]+DP[N-3]+...+DP[1])=\) \(2^{2}(DP[N-3]+DP[N-4]+...+DP[1])\) \(= 2^{3}(DP[N-4]+DP[N-5]+...+DP[1])... =2^{N-2}DP[1]\) 가 나옵니다.

DP[1] = 1 이기 때문에 답은 \(2^{N-2}\) 가 됩니다.

각 테스트 케이스마다 \(2^{n-2}\) 구해주면 되지만 계속 2씩 곱하면 \(N\)이 최대 10억이기 때문에 시간이 터지게 됩니다. 그래서 분할정복으로 \(O(logN)\) 만에 구해야 합니다.

 

기본적으로 우리가 \(a^{b}\)를 구하는 방법은 \(a\)를 \(b\)번 곱하는 방법입니다.

하지만 b가 짝수라면 \(a^{b/2}\ * a^{b/2} = a^{b}\), \(b\)가 홀수라면 \(a^{b/2}*a^{b/2}*a = b\) 임을 이용해보면 한번 곱할때마다 2배씩 줄어든다는 것을 알 수 있습니다. 이것을 활용해보면 \(O(logN)\) 만에 \(a^{b}\) 를 구할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mpow(int x) {
    if(!x) return 1;
    ll tmp = mpow(x/2);
    return (tmp*tmp*(x % 2+1)) % 1000000007;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n,T;
    cin >> T;
    while(T--) {
        cin >> n;
        if(n == 1) cout << 1 << '\n';
        else cout << mpow(n-2) << '\n';
    }
}