11726번 2×n 타일링

뻔한·2020년 4월 15일
0

Dynamic programming

목록 보기
6/16

문제 링크

2×n 타일링

문제 풀이

01타일 처럼 문제를 풀어보면 피보나치 수열이다.

구현

#include <iostream> 
#include <cstring>
using namespace std;
int N, cache[1001];

int solve(int n) {
    if (n <= 2) return n; 
    int& ret = cache[n];
    if (ret != -1) return ret;
    ret = (solve(n - 1) + solve(n - 2)) % 10007;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    memset(cache, -1, sizeof(cache));
    cout << solve(N);
    return 0;
}
profile
ㄷㄷㄷㅈ

0개의 댓글