1904번 01타일

뻔한·2020년 4월 15일
0

Dynamic programming

목록 보기
5/16

문제 링크

01타일

문제 풀이

점화식을 세워보면 피보나치 수열이다. 피보나치 수열에서 15746로 나누는 것만 추가해주면 된다.

구현

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

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)) % 15746;
    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개의 댓글