백준 11726 : 2 × n 타일링

문제 링크입니다 https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

2 × n 크기의 직사각형에 타일을 채울 때, 맨 오른쪽 열에는 세로 블록 1개가 오는 경우, 가로 블록 2개가 오는 경우 두 가지밖에 있을 수가 없습니다. 예를 들어, 2 × 5 타일의 경우는 다음과 같습니다.

 

 

그러므로,

 

[1] 세로 블록 1개가 오는 경우 : 2 × (n-1) 크기의 직사각형에 타일을 채우는 방법의 수

[2] 가로 블록 2개가 오는 경우 : 2 × (n-2) 크기의 직사각형에 타일을 채우는 방법의 수

→ 2 × n 크기의 직사각형에 타일을 채우는 방법의 수 = [1] + [2] 

 

결국, "D[N] : 2 × N 크기의 직사각형에 타일을 채우는 방법의 수" 라 한다면,

∴ D[N] = D[N - 1] + D[N - 2] 라는 점화식을 얻게 됩니다!

 

 

[소스코드]

 

#include<cstdio>
 
int n, dp[1001];  // dp[n] : 2 x n 크기의 직사각형에 타일을 채우는 경우의 수
 
int main(void) {
    scanf("%d", &n);
 
    // 2 x 1을 채우는 경우의 수는 1, 2 x 2를 채우는 경우의 수는 2 입니다
    dp[1] = 1, dp[2] = 2;
 
    // 3부터 주어진 수(n)까지 타일을 채우는 경우의 수를 모두 구해줍니다
    // 단, 문제에서 주어진대로 10007로 나눈 값을 저장합니다
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
        dp[i] %= 10007;
    }
    printf("%d", dp[n]);
    return 0;
}