[Baekjoon] 2 x N 타일링

👀 문제 설명

문제

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

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

 

입력

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

 

출력

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

 

예제 입력 1

2

 

예제 출력 1

2

 

예제 입력 2

9

 

예제 출력 2

55

 

✍🏻풀이

세로 2는 고정이고, 가로가 n값이므로, 가로 n을 1과 2로 어떻게 구성하느냐를 생각했다.

위의 이미지처럼 가로의 구성이 결정되면, 세로의 구성도 자동으로 결정되므로 가로만 생각해주면 된다.

 

n을 1과 2로 구성하는 경우의 수를 dp[n]에 저장한다.

dp[n]의 규칙을 찾아보면, 

이런 점화식이 나온다.

그림으로 생각해보면, 

이런 규칙이 나온다.

이 점화식을 사용해 dp[n]까지 구하고, dp[n]을 출력하면 된다.

 

문제에서 dp[n]을 10,007로 나눈 나머지를 출력하라고 해서 나는 출력을 할 때 dp[n] % 10007을 했는데, 이렇게 하면 답이 틀리다고 나온다..!

그래서 애초에 dp값을 정할 때, dp[n] = (dp[n - 1] + dp[n - 2]) % 10007 로 넣었더니 맞는 답이 되었다.

 

코드

#include <stdio.h>
#include <iostream>

using namespace std;

int n;
int dp[1001];

int main() {
    cin >> n;
    
    dp[0] = 1; dp[1] = 1;
    dp[2] = 2; dp[3] = 3;
    for (int i = 4; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
    }
    
    cout << dp[n] << endl;
    
    return 0;
}