[ALGOSPOT] 타일링 (TILING2)

algospot.com/judge/problem/read/TILING2

algospot.com :: TILING2

<문제>

2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요.

예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다.

경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요.

 

<입력>

입력의 첫 줄에는 테스트 케이스의 수(C <= 50)가 주어집니다. 그후 C줄에 각각 1개의 자연수로 n(1 <= n <= 100)이 주어집니다.

 

<출력>

각 테스트 케이스마다 한 줄에 경우의 수를 1000000007로 나눈 나머지를 출력합니다.

 

<예제 입력>

3

1

5

100

 

<예제 출력>

1

8

782204094

 

몇가지 케이스를 들여다보면 규칙을 찾을 수 있다.

현재의 부분 답은

1만큼 작은 부분답에 2*1(세로로 1개) 만큼의 타일을 붙인 갯수 + 2만큼 작은 부분답에 2*2(가로로 2개) 만큼의 타일을 붙인 갯수임을 알 수 있다.

 

1. Bottom-Up

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int tc;
    cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        vector<int> v(n+1, 0);
        v[1] = 1;
        v[2] = 2;
        v[3] = 3;
        for(int i=4;i<=n;i++)
            v[i] = (v[i-1]+v[i-2])%1000000007;
        cout<<v[n]<<endl;
    }
    return 0;
}

2. Top-down

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int tiling[101];
 
int get_tiling(int pos)
{
    if(pos<=1) return 1;
    int& ret = tiling[pos];
    if(tiling[pos]!=0) return tiling[pos];
    return tiling[pos] = (get_tiling(pos-1)+get_tiling(pos-2))%1000000007;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int tc;
    cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        memset(tiling, 0, sizeof(tiling));
        cout<<get_tiling(n)<<endl;
    }
 
    return 0;
}

 

코드를 보면 아시겠지만 피보나치 수열과 같은 성질을 가지고 있습니다.