[👊DP뿌시기 #1] (BOJ 11726) 2 X N 타일링

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

11726번: 2×n 타일링

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

 

출력

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

 

 

---

접근법

처음부터 차근차근 생각해보자.

가로의 길이가 1일 때부터 생각을 해보면 다음과 같은 경우가 발생한다.

 

무엇인가 규칙이 발생하는거 같기도 하고??

 

그러면 이렇게 한번 생각해보자

가로의 길이가 N인 타일은 어떻게 완성이 되는 것일까?

 

먼저 N-1에서 N이 되려면 어떻게 해야할까?

당연히 가로가 1인 타일을 넣으면 된다.

 

그러면 N-2에서 N이 되려면??

가로가 1인 막대 2개인 경우 + 세로가 2인 막대 2개 ??

 

N-2에서 N이 되는 경우는 1가지 이다.

왜냐하면 N-1에서 N이 되는 경우에 가로가 1인 막대 2개인 경우가 포함되기 때문

 

따라서, N이 되는 경우 = N-1인 경우 + N-2인 경우

 

그러면 왜 N-3부터는 포함시키지 않는 것이죠??

 

N-3인 경우는 N-1인 경우에 포함되기 때문에 이를 제외한 것입니다.

 

코드

#include <iostream>

using namespace std;

int N;

int d[1002];

int main(void){
    cin >> N;
    d[1] = 1;
    d[2] = 2;

    for(int i=3;i<=N;i++){
        // 10007로 나눈 나머지를 출력하라고 명시되어 있음
        d[i] = (d[i-1] + d[i-2])%10007;
    }

    cout << d[N];
}