백준 15243 (C++) Tiling

최초 업로드: 2025-08-28 00:18:16

최근 수정 시간: 2025-08-28 00:18:56

게시자: rlatjwls3333

카테고리: 백준

# [Gold V] Tiling

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

## 문제 설명

Domino tiles (or dominoes) are rectangular pieces of size 2x1. Each square contains a number from 1 to 6. These pieces are used to play a game but in this problem we are going to use them for something different.

We can build rectangles of certain width W and height 3 using dominoes. We are wondering how many ways of creating such rectangles are possible.

Below you can see the three possible ways of creating a rectangle of width 2 and height 3.

As you see there are many ways of tiling the rectangle. For example this is a possible solution with width 12:

Your task is to write a program that computes the number of possible ways of tiling a rectangle of width W and height 3.

## 입력

A single line with an integer W. The width of the rectangle.

The value of W will be between 1 and 1000.

## 출력

A single line with the number of possible ways. The numbers can be large so print the solution modulo 1000000007 (109 + 7).

## 풀이
3*w인 직사각형에 2 * 1인 타일을 채워넣는 타일링 문제이다.  
$dp[i] = dp[i-2]*3+2 + (dp[i-4] + dp[i-6] + ... + dp[2]) * 2$라는 규칙이 적용된다.

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

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

ll w[1001];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;

w[2]=3;
 for(int i=4;i<=n;i+=2) {
 w[i] = (w[i-2]*3+2)%MOD;
 for(int j=2;j<i-2;j+=2) w[i] = (w[i]+w[j]*2)%MOD;
 }
 cout << w[n];
}
```