[BOJ] 1309_동물원

동물원

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

1309번: 동물원

 

분류를 보니 Dynamic Programming 문제이다.
규칙을 찾기 위해 1부터 4까지 노가다를 해보자.
a1 = 3
a2 = 7
a3 = 17
a4 = 41
...
여기까지 수행을 한 후 규칙을 추측해보자.
an = an-1 * 2 + an-2

이를 적용해서 코드를 정리해보자.

우연히 바로 정답이 떠서 당황했다...

 

• 정답 코드

    #include<iostream>
    using namespace std;
    #define MOD 9901
  
    int dp[100000] = { 0, };
  
    int main() {
        int n;
        cin >> n;
        dp[0] = 1;
        dp[1] = 3;
        for (int i = 2; i <= n; i++) 
            dp[i] = (2 * dp[i - 1] + dp[i - 2]) % MOD;
  
        cout << dp[n] << endl;
        return 0;
    }

 

---