(11727)(DP) 백준 2xn 타일링 2

https://www.acmicpc.net/problem/11727

풀이

---

기존의 2xn타일링 문제에서 2x2타일이 추가된 형태이다.

기존 문제에서 2xn 크기의 직사각형을 1x2타일과 2x1타일을 이용해 채웠을때

dp[n] = dp[n-1] + dp[n-2]; 과 같은 식이 성립했다.

그 이유는 dp[n-1]까지의 타일 끝에 2x1의 타일을 이어 붙이는 경우 / dp[n-2]까지의 타일 끝에 1x2타일 두장을 이어 붙이는 경우를 더해 dp[n]의 타일의 경우의 수가 도출

되었기 때문이다. 

 <<< --- 타일링 2 문제에서는 n-2까지의 타일에 이어 붙이는 2x2 사각형의 경우가 1x2타일 2 개와 2x2타일 1 개를 이어 붙이는 경우로 나누어 지기 때문에

타일링 2 문제의 경우에서는

dp[n] = dp[n-1] + dp[n-2] * 2 ; 라는 식이 성립하게 된다. 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
 
int main() {
    int dp[1001] = { 0 };
    int N;
 
    scanf("%d", &N);
 
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= N; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2] * 2)%10007;
    }
 
    printf("%d", dp[N]);
 
    return 0;
 
}