알고리즘/백준
[백준] 11727 2×n 타일링 2 c++
오오오니
2022. 9. 3. 15:11
https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
#include<iostream>
using namespace std;
int main()
{
int n;
int dp[1001];
cin >> n;
dp[0] = 0;
dp[1] = 1;
dp[2]=3;
for (int i = 3; i <= n; i++)
{
if (i % 2)//홀수면
dp[i] = (dp[i - 1] + dp[i - 2]*2) % 10007;
else//짝수면
dp[i] = (dp[i - 2] * 3+ dp[i-3]*2) % 10007;
}
cout << dp[n];
}