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

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

11726번: 2×n 타일링

 

해설:

다이나믹 프로그래밍을 사용하여 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제

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

2. 다이나믹 프로그래밍을 활용하여 이전 단계의 값을 이용해 현재 단계의 값을 계산.

3. a[i]를 구하는 과정에서 a[i-1]은 현재 단계에서 가장 오른쪽에 1×2 타일을 놓은 경우를 의미하고, a[i-2]는 현재 단계에서 가장 오른쪽에 2×1 타일을 놓은 경우를 의미함.

4. 두 경우를 합산하여 a[i]를 구하고, 값이 매우 큰 경우를 대비해 10007로 나눈 나머지를 저장.

 

---

코드:

#include <stdio.h>
using namespace std;

int main(){    
    int a[1001];  // 각각의 크기에 대한 채우는 방법의 수를 저장하는 배열
    int n;
    scanf("%d", &n);
    // 초기값 설정
    a[1] = 1; // 1×2 크기의 직사각형을 채우는 방법은 1가지
    a[2] = 2; // 2×2 크기의 직사각형을 채우는 방법은 2가지 (가로 2개 또는 세로 2개의 타일로 채울 수 있음)
    
    // 다이나믹 프로그래밍을 이용하여 나머지 경우의 수 계산
    for (int i = 3; i <= n; i++)
    {
        // 이전 단계에서 가장 오른쪽에 1×2 타일을 놓은 경우의 수와
        // 이전 단계에서 가장 오른쪽에 2×1 타일을 놓은 경우의 수를 합산하여 현재 단계의 경우의 수를 계산
        a[i] = (a[i-1] + a[i-2]) % 10007;
    }
    printf("%d", a[n]);
    return 0;
}