[백준] 11726번. 2×n 타일링 C++

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.  짝수, 홀수일 때를 나눠서 홀수면 1*2 타일이 하나 추가되고, 짝수면 그 전 짝수(n-2)에서 2가지 경우가 추가되는 식으로 생각했다. 이렇게 생각하면 문제가, n=4라 하면 <1*2 + 2*2(2*1 2개) + 1*2> 이 경우가 고려되지 않는다.

 

2. 짝홀일 때를 나누지 않고 다시 생각해보자!

 n=4일 때 n=2의 타일들에 2*2(2*1 2개) 타일을 붙이고, n=3의 타일들에 1*2 타일을 붙이면 된다.

이걸 점화식으로 표현하면 dp[i] = dp[i-2] + dp[i-3]이다. (피보나치랑 같음..ㅎ)

 

코드는 간단하다!!

#define MOD 10007
#define MAXN 1001
#include <iostream>
#include <string.h>
using namespace std;

int n;
int dp[MAXN];

int main()
{
    cin>>n;
    
    dp[1] = 1;
    dp[2] = 2;
    
    for(int i=3; i<=n; i++){
        
        dp[i] = (dp[i-1] + dp[i-2])%MOD;
        
    }
    
    cout<<dp[n]<<"\n";

    return 0;
}