[DP] 11726번 2xn 타일링

11726번 2xn 타일링

 

https://www.acmicpc.net/problem/11726

 

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

입력

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

 

출력

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

 

예제 입력

2

9

 

예제 출력

2

55

 

해결방법

순환식을 찾아 문제를 해결하는 DP 문제이다

 

 

⭐️ 솔루션 ⭐️

2xn의 직사각형에서 오른쪽의 타일들을 빼서 이 전의 경우를 만든다고 가정해보자

만약 2x1 타일이 하나 있다면 이는 2 x (n-1) 의 경우일 것이다

또한 1x2 타일이 두개 있다면 이는 2 x (n-2) 의 경우일 것이다

따라서 순환식은 d[n] = d[n-1] + d[n-2] 가 성립된다

 

 

 

소스코드

1️⃣ Top-down

#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#define MAX 1001
using namespace std;

int n;
int d[MAX];

/*

 순환식 : d[n] = d[n-1] + d[n-2]
 
*/

int dp(int i){
    if(i==1) return 1;
    if(i==2) return 2;
    
    if(d[i] > -1){
        return d[i];
    }else{
        d[i] = dp(i-1) + dp(i-2);
        return d[i] % 10007;
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    memset(d, -1, sizeof(d));
    
    cout << dp(n) << "\n";
    
    return 0;
}

 

2️⃣ Bottom-up

#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#define MAX 1001
using namespace std;

int n;
int d[MAX];

/*

 순환식 : d[n] = d[n-1] + d[n-2]
 
*/

int dp(){
    d[1] = 1;
    d[2] = 2;
    
    for(int i=3; i<=n; i++){
        d[i] = (d[i-1] + d[i-2]) % 10007;
    }
    
    return d[n];
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    cout << dp() << "\n";
    
    return 0;
}