![]
문제링크: 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] 이라고 적어주었는데.... 자꾸 &을 넣지 않아 실수를 한다. 더욱 집중하자.