11727번-2*n 타일링2

문제

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

---

접근방법

1) 접근 사고

11726번과 유사하다 가로만 봐주기 때문에 n - 2인 경우를 하나 더 더 해주면 된다. 왜냐하면 2*2 타일의 가로는 2이기 때문이다.

 

2) 시간 복잡도

O(n)

3) 배운 점

11726번 응용 정도인거 같다.

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 1001;
const int mod = 10007;
int n;
int cache[MAX];
 
int search(int width)
{
    if(width == 0)
        return 1;
 
    if(width < 0)
        return 0;
 
    int &ret = cache[width];
    if(ret != -1)
        return ret;
    ret = (search(width - 1) + search(width - 2) + search(width - 2)) % mod;
    return ret;
}
 
int main(void)
{
    fastio;
    cin >> n;
 
    memset(cache, -1, sizeof cache);
    cout << search(n) << "\n";
}