repl.it
@TaeHunKim/

TILING2-Answer

C++11

No description

fork
loading
Files
  • main.cpp
main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

const int MOD = 1000000007;
int cache[101];

// 2*width 크기의 사각형을 채우는 방법의 수를 MOD 로 나눈 나머지를 반환한다
int tiling(int width) {
	// 기저 사례: width 가 1 이하일 때
	if(width <= 1) return 1;
	// 메모이제이션
	int& ret = cache[width];
	if(ret != -1) return ret;
	return ret = (tiling(width-2) + tiling(width-1)) % MOD;
}

int main()
{
    vector<int> input_v = {1, 5, 100};
    vector<int> expected_output_v = {1, 8, 782204094};
	memset(cache, -1, sizeof(cache));
	for(int i = 0; i < input_v.size(); i++) {
        int input = input_v[i];
        int expected = expected_output_v[i];
        int output = tiling(input);
        if (expected == output)
		    cout << input << ": " << output << endl;
        else
            cout << input << ": expected " << expected << ", actual " << output << endl;
    }
}
Fetching token
?