백준 19587번 객실 배치 - C++(cpp) 풀이

---

 

1. N층짜리 건물에 객실을 배치하는 방법의 수를 점화식으로 나타낸다.
2. 점화식을 행렬의 곱으로 나타낸다.
3. 분할정복을 이용하여 행렬의 거듭제곱을 계산한다.

 

1. N층짜리 건물에 객실을 배치하는 방법의 수를 점화식으로 나타낸다.

 T(n) = N층짜리 건물에 객실을 배치하는 방법의 수

 T(n) = A(n) + B(n) + C(n)
 A(n) = n층은 비워두는 경우의 수
 B(n) = n층은 1호실을 채우는 경우의 수
 C(n) = n층은 2호실을 채우는 경우의 수

 

 n번째 층의 상태에 따라 n-1번째 층의 상태를 결정하는 경우가 달라진다.

1. n번째 층이 비어있다면: n-1번째 층은 비울수도, 1호실만 채울수도, 2호실만 채울수도 있다.
2. n번째 층의 1호실을 채웠다면: n-1번째 층은 비우거나 2호실만 채울 수 있다.
3. n번째 층의 2호실을 채웠다면: n-1번째 층은 비우거나 1호실만 채울 수 있다.

 A(n) = A(n-1) + B(n-1) + C(n-1)
 B(n) = A(n-1) + C(n-1)
 C(n) = A(n-1) + B(n-1)

 

 이때 1호실만 채우는 경우와 2호실만 채우는 경우는 대칭이므로 B(n) = C(n)이다. 따라서 아래와 같은 점화식으로 표현할 수 있다.

 Count(n) = A(n) + 2*B(n)
 A(n) = A(n-1) + 2*B(n-1)
 B(n) = A(n-1) + B(n-1)

 

2. 점화식을 행렬의 곱으로 나타낸다.

 N=10^18이므로 점화식을 순차계산하면 시간초과가 발생한다. 점화식을 빠르게 계산할 수 있는 방법으로 행렬의 곱을 활용하는 방법이 있다. 위의 점화식을 행렬곱으로 표현하면 아래와 같다. [An, Bn]은 [[1, 2], [1, 1]]이라는 2X2행렬을 n-1번 거듭제곱한 뒤, [A1, B1]인 [1, 1]과 곱해준 결과가 된다.

 

3. 분할정복을 이용하여 행렬의 거듭제곱을 계산한다.

 MxM 행렬의 N 거듭제곱을 순차 계산하면 O(M^3 * N)의 시간복잡도가 들게 된다. 따라서 N=10^18로는 시간초과가 발생하게 된다. 하지만 분할정복을 이용하여 구현하면 O(M^3 * logN)에 계산이 가능하다. 

반응형

---

#include <iostream>

using namespace std;

typedef pair<long long, long long> pll;
typedef pair<pll, pll> matrix22;

long long MOD = 1000000007;
long long N;
matrix22 A = {{1, 2}, {1, 1}};

matrix22 multiply(matrix22 a, matrix22 b) {
    matrix22 ret = {{0, 0}, {0, 0}};
    
    ret.first.first += a.first.first * b.first.first % MOD; ret.first.first %= MOD;
    ret.first.first += a.first.second * b.second.first % MOD; ret.first.first %= MOD;
    
    ret.first.second += a.first.first * b.first.second % MOD; ret.first.second %= MOD;
    ret.first.second += a.first.second * b.second.second % MOD; ret.first.second %= MOD;
    
    ret.second.first += a.second.first * b.first.first % MOD; ret.second.first %= MOD;
    ret.second.first += a.second.second * b.second.first % MOD; ret.second.first %= MOD;
    
    ret.second.second += a.second.first * b.first.second % MOD; ret.second.second %= MOD;
    ret.second.second += a.second.second * b.second.second % MOD; ret.second.second %= MOD;
    
    return ret;
}

matrix22 power(long long n) {
    if (n == 1) return A;
    
    matrix22 half = power(n/2);
    
    if (n % 2 == 0) return multiply(half, half);
    else return multiply(multiply(half, half), A);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    if (N == 1) cout << 3;
    else {
        matrix22 A_pow = power(N-1);
        
        long long an = (A_pow.first.first + A_pow.first.second) % MOD;
        long long bn = (A_pow.second.first + A_pow.second.second) % MOD;
        
        cout << ((2 * bn % MOD) + an) % MOD;
    }
    
    return 0;
}