종만북 2n 타일링 C++ 풀이 (코드제공)

1. 문제 설정 확인

종만북에서도 ‘고전적인 DP문제’ 로 규정하고 있을 만큼, 간단한 2n 타일링 문제이다.

3. 해답 코드

#include <iostream>
#include <string.h>
using namespace std;
const int MOD = 1000000007;
long long cache[101];
int solution(int k){
    if (k == 1 || k == 0)
        return 1;
    if (k == 2)
        return 2;
    long long& ret = cache[k];
    if (ret != -1)
        return ret % MOD;
    ret = solution(k-1) + solution(k-2);
    return ret % MOD;
}
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        memset(cache, -1, sizeof(cache));
        int k;
        cin >> k;
        cout << solution(k) << endl;
    }
}

Source

• 종만북, 2022.07.22
• CLion