[백준 11726] 2xN 타일링

문제설명

n의 값을 입력 받고 타일로 채우는 방법의 수를 출력하는 문제이다. 단, 출력시 10007로 나눈 나머지를 출력시킨다.

---

알고리즘

1. n의 값을 입력 받는다.
2. bottom-up방식으로 배열에 값을 저장 하는데 런타임 에러방지를 위해 10007로 나눈 나머지를 저장한다.
3. 해당하는 값을 출력한다.

---

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

using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;    // n값 입력
    int arr[1001];

    arr[0] = 1;
    arr[1] = 2;

    for (int i = 2; i < N; i++)
        arr[i] = (arr[i - 1] + arr[i - 2])%10007;

    cout << arr[N - 1] << "\n";

    return 0;
}

풀이 규칙

N의 값	가능한 방법의 수
1	1
2	2
3	3
4	5
5	8
6	13
7	21
8	34
9	55

위와 같은 방식으로 전개 되는데 뒤의 두 항을 더하면 현재 값을 구할 수 있다는 규칙을 가지고 있다.

고찰

이번 문제는 다이나믹 프로그래밍 알고리즘의 bottom-up 방식으로 풀이가 가능하다.
간단하게 규칙을 작성하면 풀 수 있는 문제였다.