BOJ 11727번 : 2xn 타일링 2 / C언어

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

11727번: 2×n 타일링 2

 

해설:

1. 배열 a는 각 2×i 크기의 직사각형을 채우는 방법의 수를 저장.

2. a[i]는 2×i 크기의 직사각형을 채우는 방법의 수를 의미. 주어진 너비 n을 입력으로 받고, 초기값으로 a[1] = 1, a[2] = 3을 설정.

3. 이는 각각 2×1 크기와 2×2 크기의 직사각형을 채우는 방법의 수를 의미.

4. 3번째부터 n까지의 직사각형을 채우는 방법의 수를 구해야함. 이때, 다이나믹 프로그래밍의 핵심 아이디어는 이전 단계의 결과를 활용하여 현재 단계의 결과를 계산하는 것임. 따라서 a[i]를 구할 때는 a[i-1], a[i-2]의 값을 활용.

5. 마지막으로 계산된 a[n]을 출력합니다.

 

---

코드:

#include <stdio.h>
using namespace std;

int main(){
    int a[1001]; // D[i] = 2 x i 크기의 직사각형을 채우는 방법의 수
    int n;
    scanf("%d", &n);

    // 초기값 설정
    a[1] = 1; // 2 x 1 직사각형을 채우는 방법은 1가지
    a[2] = 3; // 2 x 2 직사각형을 채우는 방법은 3가지

    // 다이나믹 프로그래밍을 사용하여 2 x n 직사각형을 채우는 방법의 수 계산
    for (int i = 3; i <= n; i++)
    {
        // 현재 단계의 결과를 이전 단계의 결과를 이용하여 계산
        // 1 x 2 타일 하나를 추가하는 경우: a[i-1]
        // 2 x 1 타일 두 개를 추가하는 경우: a[i-2]
        // 2 x 2 타일 하나를 추가하는 경우: a[i-2]
        // 이들을 모두 더한 값에 10007로 나눈 나머지를 취함
        a[i] = ((a[i-1] + a[i-2] + a[i-2])  % 10007);
    }
    printf("%d", a[n]);
    return 0;
}