백준 11726 2Xn 타일링 [c++]

6 Feb 2024 ~ 5 Feb 2024 • Hun

2Xn 타일링 실버3

문제

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

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

문제 풀이

1~5까지 그려보니 피보나치임을 알 수 있었다. 그래서 dp로 풀었다. 금방 풀었다. 그런데 10007로 나눈 나머지를 출력해야 하는데 dp를 계산할 때 적용해도 동일한 결과가 나옴을 알 수 있었다.

modulo 특징 적용!

코드

#include <iostream>
using namespace std;

int tile[1002];

void dp(int n)
{
    tile[1] = 1;
    tile[2] = 2;
    for(int i = 3; i <= n; i++)
    {
        tile[i] = (tile[i-1] + tile[i-2]) % 10007;
    }
}

int main()
{
    int n;
    cin >> n;

    for(int i = 0; i <= 1000; i++)
    {
        tile[i] = 0;
    }
    
    dp(n);

    cout << tile[n] << endl;

    return 0;
}

총평

Easy.
but 조건 잘 읽자.

ps
dp