[백준 11726번] 2×n 타일링 풀이

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

이 문제는 점화식만 생각해낸다면 상당히 빠르게 풀 수 있는 문제이다.

 

n=1, n=2

 

n=1일 때와 n=2일때만 생각해보면 이런식으로 1개, 2개가 가능하다.

 

n=3일 때는  n=2인 경우에 2x1 한 개를 오른쪽에 붙이거나

n=1인 경우에 1x2 두 개를  오른쪽에 붙이는 경우를 생각해 볼 수 있다.

n=3

 

같은 방식으로 n=4일 때는 2x1 한개를 n=3인 경우의 오른쪽에 붙이거나

1x2 두개를 n=2인 경우의 오른쪽에 붙이는 경우를 생각해 볼 수 있다.

 

n=4

 

 

결국 n=k일 때 개수는 n=k-1 일 때와 n=k-2일 때의 경우를 합하면 된다.

 

그래서 이에관하여 코드를 작성해보면

 

#include <iostream>
using namespace std;

int dp[1001] = {0};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    dp[1]=1;
    dp[2]=2;
    for(int i=3; i<=n; i++){
        dp[i]=(dp[i-1]+dp[i-2])%10007;
    }
    cout<<dp[n];
}

 

이와 같이 작성할 수 있다.