[백준/c++] 11727번: 2xn 타일링2

문제 링크 - https://www.acmicpc.net/problem/11727

🌱 문제

🌱 풀이

• d[n]도형은 그전의 도형에서 오른쪽 끝에 가로길이가 2인 도형두개가 오거나 그전 도형에서 오른쪽 끝에 가로길이가 1인 도형 한개가 오는 경우가 있다.
• 이때, 가로길이가 2인 도형이 오는 경우는 2x2 도형이오거나 2x1도형 두개가 두개 오는 경우 이렇게 총 2가지 이다.
• 점화식은 d[n]=d[n-1]+d[n-2]x2 이다.

🌱 코드

//11727번: 2*n 타일링 2
//그리면서 노가다로 찾음...

/*
풀이방법

d[n]도형은 그전의 도형에서 오른쪽 끝에 가로길이가 2인 도형두개가 오거나
그전 도형에서 오른쪽 끝에 가로길이가 1인 도형 한개가 오는 경우가 있다.
이때 가로길이가 2인경우는 2x2 도형이오거나 2*1도형 두개가 두개 오는 경우 이렇게 총 2가지 이므로
점화식은 d[n]=d[n-1]+d[n-2]*2 이다.
*/

#include <iostream>
using namespace std;

int d[1001];

int main(){
    int n;
    cin>>n;

    d[1]=1;
    d[2]=3;
    for(int i=3; i<=n; i++){
        d[i]=(d[i-1]+d[i-2]*2)%10007;
    }
    cout<<d[n]<<"\n";
}