[동적계획법] 11. 비대칭 타일링

https://algospot.com/judge/problem/read/ASYMTILING

algospot.com :: ASYMTILING

 

컨셉

asytiling(n) //대칭 빼고 채우는 방법의 수

tiling(n)     //타일을 채우는 방법의 수

asytiling(n) = tiling(n-1) + tiling(n-2) - tiling(n/2) - (짝수인경우만) tiling(n-1/2);

⇒ asytilng(n) = tiling(n) - tiling(n/2) - (짝수인경우만) tiling( (n-1) /2);

 

초안

내가 쓴 답(정답, 0ms)

 

#include <iostream>
#include <memory.h>
using namespace std;
const int MOD = 1000000007;
int cache[100+1];
int cache2[100+1];
 
//n만큼의 길이를 2x1 타일로 채우는 방법의 수
int tiling(int n)
{
    if(n<=1) return 1;
    int& ret = cache[n];
    if(ret != -1) return ret;
 
    return ret = ((tiling(n-1) + tiling(n-2)) % MOD);
}
 
 
//대칭 빼고 n만큼의 길이를 타일로 채우는 방법의 수
int asytiling(int n)
{
    if(n <= 2) return 0;
    int& ret = cache2[n];
    if(ret != -1) return ret;
 
    ret = tiling(n);
    ret = (ret - tiling(n/2) + MOD) % MOD;
    if(n%2 == 0) ret = (ret - tiling((n-1)/2) + MOD ) % MOD;
    return ret;
}
 
int main()
{
    int C;
    cin >> C;
 
    int n;
    while(C--)
    {
        memset(cache, -1, sizeof(cache));
        memset(cache2, -1, sizeof(cache2));
        cin >> n;
        cout << asytiling(n) << endl;
    }
}

 

주의

 if(n%2 == 0) ret = (ret - tiling((n-1)/2) + MOD ) % MOD;

 return ret;

 

을 할 때, tiling(n-1/2) 라고 했더니 n - 0.5가 되어버렸다. 계산에 괄호 붙여줄 것!