[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}\ast a^{b/2}=a^b$, $b$가 홀수라면 $a^{b/2}\ast a^{b/2}\ast 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';
    }
}