동물원 - 1309번

해결방법

O을 배치한 경우, X를 배치 하지 않은 경우라고 할 때 O X | X O | X X 3가지 경우의 수로 둘 수 있다. 그래서 dp를 N * 3개의 배열을 두고 시작하였다.

 int dp[100001][3]

점화식은 어떻게 될까? 점화식도 3가지로 나눌 수 있다. 만약 O X경우라면 이전의 경우의 수는 X O | X X가 되어야만 하기 때문에 아래와 같아진다. 나머지도 똑같은 방식으로 구해본다면 점화식을 구할 수 있다.
$$ dp[i][0] = dp[i-1][1] + dp[i-1][2] $$
$$ dp[i][1] = dp[i-1][0] + dp[i-1][2] $$
$$ dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] $$

전체코드

#include<iostream>
using namespace std;
int dp[100001][3], N;
const int INF = 9901;
int main() {
    cin >> N;
    dp[0][0] = dp[0][1] = dp[0][2] = 1;
    for (int i = 1; i < N; ++i) {
        dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) %INF;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % INF;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % INF;
    }
    cout << (dp[N-1][0] + dp[N-1][1] + dp[N-1][2]) %INF << '\n';
    return 0;
}