1309

백준 1309번

Link: 1309번: 동물원

---

문제 설명

오늘은 DP를 배워서 이제 한동안 DP문제에 매달릴 예정이다.

그 중에서도 아주 간단한 문제를 하나 풀었다.

정말 기본적인 문제라고 할 수 있는데, 몇개 케이스 따져보며 규칙 찾으면 바로 풀리는 문제다.

역시 DP문제답게 규칙만 찾으면 구현은 간단히 끝난다.

이번 기회에 DP에 대해 확실히 정복하고 갈 작정이다.

여전히 갈길이 멀지만, 화이팅.

---

정답 코드

///
// Created by Keith_Lee on 25/02/2019.
//

#include <iostream>
#include <strings.h>

using namespace std;

int N;

long long zoo(int n){
    long long DP[n+1];
    bzero(DP, sizeof(DP));

    DP[0] = 0;
    DP[1] = 3;
    DP[2] = 7;

    for(int i=3; i<=n; i++){
        DP[i] = (2 * DP[i-1] + DP[i-2]) % 9901;
    }

    return DP[n];
}

int main(){
    cin >> N;

    cout << zoo(N) << '\n';
}

---