[백준 11727, c++] 2xn 타일링2(dp,topDown,bottomUp)

문제 번호

• 11727(https://www.acmicpc.net/problem/11727)

문제 및 입/출력

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

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

2x17

입력

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

 

출력

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

 

예제 입력1

2

예제 출력1

3

예제 입력2

8

예제 출력2

171

예제 입력3

12

예제 출력3

2731

 

문제 풀이

BOJ 11726(2xn 타일링) 문제에서 조건이 하나 더 늘어난 형태의 문제이다.

조건인 2x2 타일이 하나 더 추가되었기 때문에 앞 문제의 점화식을 수정해 주어야한다.

 

전체 타일은 1x2, 2x1, 2x2가 되었고, 이 세 가지 타일로 2xn 크기의 타일을 채우려고 할 때, 아래와 같이 분류가 된다.

 

가로 크기가 1인 타일 : 1 x 2 타일

가로 크기가 2인 타일 : 2 x 1, 2 x 2 타일

 

n-1번째 타일일 경우에는 1 x 2 타일을 한 개 붙이는 경우가 있고, n-2번째 타일일 경우에는 2 x 1 타일을 두개 붙이는 경우와 2 x 2 타일을 한개 붙이는 경우가 있다.

 

즉, 점화식은 D[n] = D[n-1] + D[n-2] * 2;

 

 

• 이 문제는 DP(Dynamic Programming)를 이용하여 풀었고, 여기서 말하는 [DP, 동적 프로그래밍]이란 큰 문제를 작은 문제로 분할하여 문제를 푸는 방법이다.
• top-down의 재귀방식과 bottom-up의 반복문 방식 두 개 모두 사용하여 풀어보았다. 

---

1. 정수 n을 입력받는다.
2. topDown 또는 bottomUp을 통해 결과값을 출력한다. 진행할 때, 문제의 요구사항에서 결과인 방법의 수를 10007로 나눈 나머지를 출력하라는 조건을 최종적으로 한번만 하는 것이아니라 arr[n]을 구할 때마다 나머지 계산을 해줘야 원하는 결과 값을 얻을 수 있다.

소스 코드

#include <iostream>
#include <stdio.h>
 
using namespace std;
 
#define MAX 1000
 
int arr[MAX + 1];
 
int topDown(int n);
int bottomUp(int n);
 
int topDown(int n) {
    if (n == 1) return 1;
    if (n == 2) return 3;
 
    if (arr[n] > 0)
        return arr[n];
 
    arr[n] = topDown(n - 2) * 2 + topDown(n - 1);
    arr[n] %= 10007;
 
    return arr[n];
}
 
int bottomUp(int n) {
    arr[1] = 1;
    arr[2] = 3;
        
    for (int i = 3; i <= n; i++) {
        arr[i] = arr[i - 2] * 2 + arr[i - 1];
        arr[i] %= 10007;
    }
    
    return arr[n];
}
 
int main() {
    int n;
    scanf("%d", &n);
 
    printf("%d\n", topDown(n));
    //printf("%d\n", bottomUp(n));
    return 0;
}