#[C++] 11722 - 2×n 타일링 2

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

---

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

using namespace std;
#include <iostream>
int dp[1001];

int tile(int x){
    if(x==1) return dp[x]=1;
    if(x==2) return dp[x]=3;
    if(dp[x]!=0) return dp[x];
    return dp[x]=(tile(x-1)+(tile(x-2)*2))%10007;
}

int main()
{
    int a;
    cin >> a;
    int result = tile(a);
    cout << result;

    return 0;
}

---

어제 했던 11726에서 좀 더 발전된 형태의 문제

앞에서 한 번 해보아서 그런가 금방 풀 수 있었다 !

역시 그림 그리는 게 최고인 것 같다. 

알고리즘은 수학적으로 머리가 팽팽팽 잘 돌아가야한다는 사실을 다시 한 번 깨닫고 간다...  ◡̎ ..

그림을 그려보니 바로 찾을 수 있었던 규칙성과 점화식 ~~~~~