11726번-2*n 타일링

문제

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

11726번: 2×n 타일링

---

접근방법

1) 접근 사고

가로만 봐주면 되는 문제이다. 왜냐하면 가로를 2간 채워서 넣을 것인지 1칸 채워서 넣을 것인지만 봐주면 되기 때문이다.

 

2) 시간 복잡도

O(n)으로 해결 간으!

 

3) 배운 점

배열에서 인덱스를 계산해주는 문제와 유사한거 같다. 규칙을 찾아서 점화식을 만들어 푸는 방법도 존재한다.

 

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)) % mod;
    return ret;
}
 
int main(void)
{
    fastio;
    cin >> n;
 
    memset(cache, -1, sizeof cache);
    cout << search(n) << "\n";
}