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

1. 문제 설정 확인

종만북 문제 링크 : ASYMTILING

저번 포스팅에 이어, 2n타일링을 응용한 비대칭 타일링 문제를 풀어보았다.

설명 작성 예정.

3. 해답 코드

#include <iostream>
#include <string.h>
using namespace std;
int n;
int MOD = 1000000007 ;
int cache[101];
int solution2(int k){
    if (k <= 1)
        return 1;
    int& ret = cache[k];
    if (ret != -1)
        return ret;
    ret = (solution2(k-1) + solution2(k-2))% MOD;
    return ret ;
}

int solution(int m){
    if(m % 2 != 0)
        return (solution2(m) -solution2(m/2) + MOD) % MOD;
    int ret = solution2(m);
    ret = (ret - solution2(m/2) + MOD) % MOD;
    ret = (ret - solution2(m/2 -1) + MOD) % MOD;
    return ret;
}

int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    for(int i =0 ; i < t; i++) {
        cin >> n;
        memset(cache, -1, sizeof(cache));
        cout << solution(n) << endl;
    }
}

Source

• 종만북, 2022.07.22
• CLion