[백준 11726] 2n 타일링

분류 : dp

 

요구사항

2*1, 1*2의 타일으로 n열의 타일을 구할 수 있는 경우의 수 구하기

 

풀이

1열은 세로 하나로 가능하다

2열은 세로 2개 혹은 가로 2개로 가능하다

 

3열은 1열에다가 2열을 붙이거나 2열에다가 1열을 붙였을 경우 가능하다

일반화 시켜보면 피보나치 수열처럼된다.

d[n] = d[n-1] +d[n-2]가 된다

 

#include <iostream>
#include <string.h>
#include <queue>
//#include "windows.h"
#include <algorithm>
#include <list>

using namespace std;
int d[1014];

int main(){
   
    int n;
    scanf("%d",&n);
    d[1]=1;
    d[2]=2;
    if(n>=3){
        for(int i=3 ; i <=n ; i++){
            d[i]= (d[i-2] +d[i-1])%10007;
        }
    }
    cout<<d[n]<<endl;
}