[DP]백준11726번 2 x n 타일링

백준11726 2xn 타일링

DP문제를 풀 때 가장 중요한 것은 문제를 쪼개서 생각할 수 있는 능력인 것 같다.

칸이 주어졌을 때, 두 가지 경우로 나누어 생각할 수 있다.

첫 번째는 2*1 타일로 채우는 경우이다.

이 경우에는 세로로 된 타일이 하나 채워지게 되는데, 세로 타일 한 개를 제외하고 N-1개의 타일이 남는다.

두 번째 경우는 1*2 타일을 배치하는 경우이다.

이 경우는 가로로 두 칸을 먹었기 때문에, 자연스럽게 아래 두 칸도 1*2 타일을 배치할 수 밖에 없게 된다.

그렇게 되면 N-2개가 남기 때문에 N-2개를 채우는 경우의 수를 더해주면 된다.

타일을 채우는 경우는 이 두 가지 밖에 없기 때문에 주어진 N 칸을 채우는 경우의 수는

N-1 ( 21 타일을 첫 칸에 배치한 경우) + N-2 (12 타일을 첫 칸에 배치한 경우) 두 가지를 더하면 된다.

#include <iostream>

using namespace std;

int N;
int arr[1001];
int main(){
    cin >> N;
    arr[1] = 1;
    arr[2] = 2;
    for(int i=3;i<=N;i++){
        arr[i] = (arr[i-1] + arr[i-2]) % 10007;
    }
    cout << arr[N];
}