백준 13976 (C++) 타일 채우기 2

최초 업로드: 2025-05-03 06:16:57

최근 수정 시간: 2025-07-25 08:46:55

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 타일 채우기 2

[문제 링크](https://www.acmicpc.net/problem/13976)

## 문제 설명

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

## 입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000,000,000,000)이 주어진다.

## 출력

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

## 풀이
#### 길이 n의 경우의 수를 an이라 할 때, an = 3an-2 + 2(an-4 + an-6 + ... + a0)이라고 할 수 있다.
#### 이 식을 an+2 = 3an + 2(an-2 + an-4 + ... + a0)와 합치면 an+2 = 4an - an-2가 도출된다.
#### n이 홀수인 경우 가능한 경우의 수가 없기에 n을 2씩 나누어주고 행렬로 나타내면 [an, an-1] = [[4, -1], [1, 0]] [an, an-1]로 나타낼 수 있다. 이를 분할정복을 이용해서 빨리 구해주면 된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9+7;

typedef vector<vector<ll>> matrix;

matrix mult(matrix a, matrix b) {
 matrix ret = { {0, 0}, {0, 0} };
 for(int i=0;i<2;i++) {
 for(int j=0;j<2;j++) {
 for(int k=0;k<2;k++) {
 ret[i][j] += a[i][k]*b[k][j];
 }
 ret[i][j] = (ret[i][j]+MOD)%MOD;
 }
 }
 return ret;
}

matrix getMatrix(matrix x, ll n) {
    if(n==1) {
        return x;
    }

matrix tmp = getMatrix(x, n/2);

if(n%2==1) {
        return mult(mult(tmp, tmp), x);
    } else {
        return mult(tmp, tmp);
    }
}

ll getCnt(ll n) {
    matrix res = getMatrix({ {4, -1}, {1, 0} }, n);
    return (res[1][0]*3+res[1][1]) % MOD;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 ll n; cin >> n;
 if(n%2==1) {
 cout << 0;
 return 0;
 }
 cout << getCnt(n/2);
}
```