[백준/C,C++] 1904번: 01타일

www.acmicpc.net/problem/1904

1904번: 01타일

점화식만 찾아낸다면 정말 간단한 문제입니다. N이 0일 경우 만들 수 있는 타일의 개수는 0개입니다. 1일 경우 1개, 2일 경우 2개라고 문제에 나와 있죠. 3은 011, 100, 111로 3개입니다. 4의 경우는 5개로 문제에 나와 있습니다. 해를 쭉 나열해보면 0, 1, 2, 3, 5인데, 피보나치 수열과 굉장히 유사합니다. 작은 문제를 쌓아 큰 문제를 푸는 상향식(Bottom-up) 동적 계획법을 이용하면 쉽게 해결할 수 있습니다.

#include<iostream>

using namespace std;

#define MAX 1000001

int DP[MAX];

int tile(int n)
{
    for (int i = 0; i < 3; i++) DP[i] = i;
    for (int i = 3; i <= n; i++) DP[i] = (DP[i - 1] + DP[i - 2]) % 15746;
    return DP[n];
}

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

    cout << tile(n) << endl;

    return 0;
}