[백준] 11727번 2xn 타일링 2

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

예제 입력 3

12

예제 출력 3

2731

 

소스코드

#include <iostream>
using namespace std;

int main() {
    int n;
    int num[1001];
    
    cin>>n;
    
    num[1]=1; num[2]=3;	// n값이 1 또는 2일 경우
    if(n>=3) {	// n값이 3이상일 경우
        for(int i=3;i<=n;i++) {	// 방법의 수는 (2x(n-1)직사각형을 채우는 방법의 수 + 1x2 타일 하나를 세우는 경우) + (2x(n-2)직사각형을 채우는 방법의 수 + 2x2 직사각형을 채우는 방법의 수)
            num[i]=(num[i-1]+num[i-2]*2)%10007;
        }
        cout<<num[n]<<endl;
    } else cout<<num[n]<<endl;
        
    return 0;
}

DP(Dynamic Programming)를 이용하여 문제를 해결하였습니다.

n이 1일 때부터 입력받은 값에 도달할 때까지의 방법의 수를 배열에 저장합니다.

저장된 값을 불러와서 구하고자 하는 방법의 수를 계산합니다.

 

2xn 직사각형을 채우는 방법의 수 = (2x(n-1) 직사각형을 채우는 방법의 수 + 2x1 직사각형을 채우는 방법의 수) + (2x(n-2) 직사각형을 채우는 방법의 수 + 2x2 직사각형을 채우는 방법의 수)