[BAEKJON] 1309 동물원

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> using namespace std; int main() { int n; scanf("%d", &n); vector<vector<int>>DP(2, vector<int>(3, 0)); for (int j = 0; j < 3; j++) DP[0][j] = 1; int k = 0; long long answer = 0; for (int j = 0; j < n - 1; j++) { DP[!k][0] = (DP[k][0] + DP[k][1] + DP[k][2]) % 9901; DP[!k][1] = (DP[k][0] + DP[k][2]) % 9901; DP[!k][2] = (DP[k][0] + DP[k][1]) % 9901; k = !k; } k % 2 == 0 ? k = 0 : k = 1; printf("%d\n", (DP[k][0] + DP[k][1] + DP[k][2]) % 9901); return 0; }