[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(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) 만에 구해야 합니다.

 

#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';
    }
}