[c++] 백준 1309 동물원

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

1309번: 동물원

간단한 dp문제이다

#include<bits/stdc++.h>
using namespace std;
#define K 9901
int dp[100100][3];
/*
dp[n][0] n번째 줄에 배치하지 않음
dp[n][1] n번째 줄의 왼쪽에만 배치함
dp[n][2] n번째 줄의 오른쪽에만 배치함
*/
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    dp[1][0] = dp[1][1] = dp[1][2] = 1;
    for(int i=2; i<=n; i++){
        // 아무것도 배치하지 않을 때
        dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2])%K;
        // 왼쪽에 배치할 때
        dp[i][1] = (dp[i-1][0] + dp[i-1][2])%K;
        // 오른쪽에 배치할때
        dp[i][2] = (dp[i-1][0] + dp[i-1][1])%K;
    }
    cout << (dp[n][0] + dp[n][1] + dp[n][2])%K;
    return 0;
}