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

문제 번호

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

문제 및 입/출력

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

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

2x5 직사각형

 

입력

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

 

출력

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

 

예제 입력1

2

예제 출력1

2

예제 입력2

9

예제 출력2

55

 

문제 풀이

2 x n 크기의 직사각형을 1x2 또는 2x1 타일로 채우는 방법의 수를 구하는 문제이다. 

 

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

 

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

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

 

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

 

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

 

n = 1, result = 1
n = 2, result = 2
n = 3, result = 3
n = 4, result = 5
...
n = 9, result = 55

 

• 즉 이 문제는 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 == 0 || n == 1)
        return 1;
    if (arr[n] > 0)
        return arr[n];
 
    arr[n] = topDown(n - 2) + topDown(n - 1);
    arr[n] %= 10007;
 
    return arr[n];
}
 
int bottomUp(int n) {
    arr[0] = 1;
    arr[1] = 1;
 
    for (int i = 2; i <= n; i++) {
        arr[i] = arr[i - 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;
}