BOJ 11727번: 2 x n 타일링 2

문제 설명

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하기

🔗 문제 링크

핵심 아이디어

1. d[n-1]에서 세로로 한 줄을 더 넣는 방법
   • 2 x 1 세로 타일 한 줄을 맨 끝에 추가

2. d[n-2]에서 정사각형을 하나 더 넣는 방법
   • 1 x 2 가로 타일 2개를 맨 끝에 추가 (세로 타일은 이미 1번에서 했을테니 제외)
   • 2 x 2 타일 1개를 맨 끝에 추가

따라서 점화식은
d[n] = d[n-1] + 2 * d[n-2]

코드

#include <bits/stdc++.h>
using namespace std;
int n;
int d[1005];

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    d[1] = 1; d[2] = 3;
    for(int i = 3; i <= n; i++){
        d[i] = (d[i-1] + 2*d[i-2])%10007;
    }
    cout << d[n];
}