[알고리즘]Algospot_TILING

출처 : https://www.algospot.com/judge/problem/read/TILING

문제

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

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

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

입력

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

출력

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

정답코드

#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

int n;

int cache[101];

// long long tiling(int num)
// {
//     if(num  <= 1) return 1;

//     long long &ret = cache[num];

//     if(ret != -1) return ret;

//     ret =  tiling(num-2) + tiling(num-1);

//     return ret % 1000000007;
// }

int main()
{
    FASTio;

    int t;

    cin >> t;

    while(t--)
    {
        cin >> n;

        memset(cache,-1,sizeof(cache));

        //cout << tiling(n) << endl;

        cache[1] = 1;
        cache[2] = 2;

        for(int i = 3; i<=n; i++)
        {
            cache[i] = (cache[i-1] + cache[i-2]) % 1000000007; 
        }

        cout << cache[n] << endl;
    }

    return 0;
}

풀이 및 사고과정

이 문제는 그나마 간단하게 해결했다.

책은 재귀를 이용해 top_down 방식의 dp를 구현했지만
나는 bottom_up 방식으로 풀어보았다.