'ㄱ'자 모양 블럭과 1∗1의 직사각형 블럭을 이용하여 2∗n 크기의 직사각형 모양으로 채우려고 한다.
가능한 방법의 수를 구하여라. 블럭은 무한정 있다고 가정한다.
이 때 숫자가 커질 수 있으므로 100,007로 나눈 나머지를 출력하시오.
#include<iostream>
using namespace std;
const int DIV = 100007;
int dp[10001] = {0, 1, 5, 11,};
int block(int n){
if(dp[n] != 0) return dp[n];
return dp[n] = (block(n - 3) * 2 % DIV +
block(n - 2) * 4 % DIV +
block(n - 1) % DIV) % DIV;
}
int main(){
int N;
cin >> N;
cout << block(N);
return 0;
}
'알고리즘' 카테고리의 다른 글
[코드업] 3719 - 블럭 채우기 6 (0) | 2020.02.29 |
---|---|
[코드업] 3716 - 블럭 채우기 5 (0) | 2020.02.29 |
[코드업] 3712 - 블럭 채우기 3 (0) | 2020.02.29 |
[코드업] 3712 - 블럭 채우기 2 (0) | 2020.02.29 |
[코드업] 3709 - 블럭 채우기 1 (0) | 2020.02.29 |