[백준] 11727 2xn 타일링2 - 다이나믹 프로그래밍

[ 문제링크 ]

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

 

🚩 조건

1. 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 구해라
2. 1 ≤ n ≤ 1,000

 

 

🚩 접근

이전에 풀었던 2xn 타일링과 유사하게 DP로 풀 수 있음

 

 

🚩 시행착오

.

 

 

💻 코드 (C++)

#include <iostream>
using namespace std;

int D[1001];    //1-indexed

int main(){
    int n;
    cin>>n;
    D[0]=1; D[1]=1;
    for(int i=2;i<=n;i++){
        D[i]=(D[i-2]*2+D[i-1])%10007;
    }
    cout<<D[n];
}