[백준 1309번] 동물원 (C++)

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

1309번: 동물원

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
int dp[100001][3];
const int MOD = 9901;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    dp[1][0] = 1; //ox
    dp[1][1] = 1; //xo
    dp[1][2] = 1; //xx

    for(int i=2; i<=N; i++)
    {
        dp[i][0] = (dp[i-1][1] + dp[i-1][2])%MOD; //xo + xx
        dp[i][1] = (dp[i-1][0] + dp[i-1][2])%MOD; //ox + xx
        dp[i][2] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2])%MOD; //ox + xo + xx
    }

    cout << (dp[N][0] + dp[N][1] + dp[N][2])%MOD;

    
}

첫째 줄에 올 수 있는 경우의 수가 아래와 같이 총 3가지이다.

OX : 왼쪽에 사자배치
XO : 오른쪽에 사자배치
XX : 배치안함

해당 경우의 수를 첫 시작값으로 갖고 이를 토대로 탐색을 이어나가게 된다.

이어서 올 수 있는 경우를 보면 다음과 같다.

OX -> XO or XX 가능
XO -> OX or XX 가능
XX -> OX or XO or XX 가능

이에 맞춰서 현재값을 기준으로 직전값에 어떤 값들이 올 수 있는 지 경우의 수를 모두 더해주면서 갱신해나가면 된다.