[BAE/<JOON> 문제풀이] 1309. 동물원 (DP.035)

https://www.acmicpc.net/submit/1309

로그인

#include <iostream>
#include <vector>

using namespace std;

int main()
{    
    vector<int> dp;
    int n;
    cin >> n;
    dp.resize(n + 1);
    int s = 3;
    dp[0] = 1;
    dp[1] = 2;
    for (int i = 2; i <= n; i++) {
        if (s * 2 < dp[i - 1]) {
            dp[i] = (s * 2) - dp[i - 1] + 9901;
        }
        else {
            dp[i] = ((s * 2) - dp[i - 1]) % 9901;
        }
        s += dp[i];
        s %= 9901;
    }
    /*for (int i = 1; i <= n; i++) {
        cout << dp[i] << endl;
    }*/
    cout << s << endl;
    return 0;
}