[동적계획법] 8. 타일링 방법의 수

 

https://algospot.com/judge/problem/read/TILING2

algospot.com :: TILING2

 

컨셉

점화식

tiling(from,end) //from부터 end까지 채우는 방법의 수

tiling(from, end) = tiling(from +1, end) + tiling(from+2, end);  //end는 다 똑같으니까 parameter에서 빼도 된다.

 

 

초안

내 코드(정답, 0ms)

/**
 * @name    8.10. 타일링2
 * @ID      TILING2
 * @date    2019-08-08
 * @author  Sunmon
 */

#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 1000000007;
int cache[100+1];
int N;
int tiling(int n)
{
    if(n<=1) return 1;
    int& ret = cache[n];
    if(ret != -1) return ret;

    return ret = ((tiling(n-1) + tiling(n-2)) % MOD);
}

int main()
{
    int C;
    cin >> C;
    while(C--)
    {
        memset(cache, -1, sizeof(cache));
        cin >> N;
        cout << tiling(N) << endl;
    }
}

 

주의

(a+b)%k == (a%k + b%k) %k