Algorithm/알고스팟
algospot - tiling2
jhg0406
2020. 2. 3. 14:05
|
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
35
36
37
38
39
40
41
42
|
//algospot - tiling2
#include <iostream>
#include <vector>
using namespace std;
#define INF 1000000007
int N;
vector<int> cache;
void init()
{
cin >> N;
cache = vector<int>(N, -1);
}
int dp(int idx)
{
if(idx == N)
return 1;
int& ret = cache[idx];
if(ret != -1)
return ret;
ret = 0;
if(idx + 1 <= N)
ret += dp(idx+1);
if(idx + 2 <= N)
ret += dp(idx+2);
ret %= INF;
return ret;
}
int main()
{
int C; cin >> C;
for(int tn = 0; tn<C; ++tn)
{
init();
cout << dp(0) << "\n";
}
}
|
cs |
https://www.algospot.com/judge/problem/read/TILING2
algospot.com :: TILING2
타일링 문제 정보 문제 2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다. 경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요. 입력 입력의 첫 줄에는 테스트 케이스의 수(C <= 50)가 주어집니다. 그후 C줄에 각각 1개의 자연수로 n(1 <= n <= 100)이 주어집니다.
www.algospot.com
TILING2
경우의수 DP문제
