백준 11726 2×n 타일링

문제

![]

문제링크: https://www.acmicpc.net/problem/11726

풀이전략

간단한 타일링문제이다. 다음의 점화식을 이용하였다.
Tiling(n) = Tiling(n-1) + Tiling(n-2)
결국 같은 모양이 반복된다는것을 알면 메모이제이션을 통해 쉽게 해결 할 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;

#define mine

int N;
int cache[1001];
const int MOD = 10007;
int tiling(int n){
    int& ret = cache[n];
    if(ret != -1) return ret;

    return ret = (tiling(n-1) + tiling(n-2))%MOD;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    memset(cache, -1, sizeof(cache));
    cache[1] = 1;
    cache[2] = 2;
    cin >> N;
    cout << tiling(N) << endl;
    
    return 0;
}

소감

실수를 안하기 위해 int& ret = cache[n] 이라고 적어주었는데.... 자꾸 &을 넣지 않아 실수를 한다. 더욱 집중하자.