[C++] BOJ 11726번: 2xn 타일링

문제 링크

문제 풀이

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 f(n)이라고 하자.

n >= 3일 때 f(n) = f(n-1) + f(n-2)이라는 식이 성립한다.

 

문제에 "첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다."라는 조건을 조심해서 풀어야 한다. 해당 식이 성립하는 것을 알고 있다면 문제를 푸는 데에 큰 문제가 없을 것이다.

(a + b) % 10007 = (a % 10007 + b % 10007) % 10007

코드

#include <bits/stdc++.h>

using namespace std;

int n;

int calced[1003];

void calc(int num)
{
    if (num > n)
        return;
    if (num == 1)
    {
        calced[1] = 1;
    }
    else if (num == 2)
    {
        calced[2] = 2;
    }
    else
    {
        calced[num] = (calced[num - 1] % 10007 + calced[num - 2] % 10007) % 10007;
    }
    calc(num + 1);
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    calc(1);

    cout << calced[n] << '\n';

    return 0;
}