[DP] 11727번 2xn 타일링2

11727번 2xn 타일링 2

 

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

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

2

8

12

 

예제 출력

3

171

2731

 

해결방법

2xn 타일링의 문제에서 2x2 타일이 추가된 문제이다.

1x2 타일 2개를 두는 경우와 2x2 타일을 1개 두는 경우는 동일한 칸을 차지한다.

따라서 D[n] = D[n-1] + 2*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] * 2
 
 */

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

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) << "\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] * 2
 
 */

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

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