TILING2 (하, p. 252)

소요 시간: 1분 이내

가장 기본적인 DP문제

이게 왜 DP문제 맨 앞에 안나오고 조금 뒤에 나온건지 잘 모르겠음.

너무 쉬운 문제라 그냥 넘어갈까 고민함.

Algospot 문제에는 그림이 안보여서 책에 있는 그림을 참고하면 되지만,

설명만 봐도 무슨 문제인지 알 수 있긴 함.

#include <bits/stdc++.h>
using namespace std;
const int M = 1e9+7;
int d[101];
int f(int x) {
    if(x<=1) return 1;
    int & ret = d[x];
    if(ret) return ret;

    return ret = (f(x-1) + f(x-2))%M;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n; cin >> n;
        memset(d,0,sizeof(d));
        printf("%d\n", f(n));
    }
    return 0;
}