[BOJ][C++] 백준 11726번: 2xn 타일링

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로 나눈 나머지를 출력한다.

 

풀이

2*n 에 채우는 경우의 수는

 

1. 2*(n-1)을 채우고 세로 직사각형(2*1) 끼우기

2. 2*(n-2)를 채우고 가로 직사각형(1*2) 두개 끼우기

 

동적계획법으로 풀이 가능하다

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 1000 + 1;
const int MOD = 10007;

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