[백준][DP] 2xn 타일링

1. 문제 주소

11726번: 2×n 타일링

 

2. 문제

n을 입력받아 2xn크기의 직사각형을 만들고 그 사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 다이내믹 프로그램 문제이다. 사각형을 그려서 규칙을 찾고 코드를 작성하였다. n=3일 때부터 가장 오른쪽 사각형이  1x2 , 2x1일 때로 나누어서 분석하면 쉽게 규칙을 찾을 수 있다.

 

3. 소스 코드

1. Bottom-up

#include <iostream>
using namespace std;
int d[1001];
 
int main(void)
{
    int n;
    cin >> n;
    
    d[1] = 1;
    d[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        d[i] = (d[i - 1] + d[i - 2]) % 10007;
    }
    cout << d[n] << '\n';
    return 0;
}

2. Top-down

#include <iostream>
using namespace std;
int d[1001];
int topdown(int n)
{
    if (n <= 2)
        return n;
    if(d[n]>0) return d[n];
    
    
    d[n] = topdown(n - 1) + topdown(n - 2);
    return d[n] % 10007;
    
 
}
 
int main(void)
{
    int n;
    cin >> n;
 
    cout << topdown(n) << '\n';
    
    return 0;
}