[백준 c++] 1309 동물원

---

문제

https://www.acmicpc.net/problem/1309
가로 2칸, 세로 N칸인 우리에 사자를 배치하려고 한다.
사자는 가로, 세로로 붙어있을 수 없다.
2 x N 배열에 사자를 배치할 수 있는 경우의 수를 구하는 문제다.
사자를 0마리 배치하는 것도 하나의 경우의 수다.

---

풀이

i번 째 열에서의 배치 가능 경우는 OX, XO, XX 다.
i+1번 째 열은 i번 째 열에 영향을 받는다.

i번 째 열이 OX일 때, i+1에서 배치 가능 경우는 XO, XX
i번 째 열이 XO일 때, i+1에서 배치 가능 경우는 OX, XX
i번 째 열이 XX일 때, i+1에서 배치 가능 경우는 OX, XO, XX

이걸 이용해서 dp 점화식을 만들면

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 n, dp[100001][3];

int main()
{
    cin >> n;
    dp[0][0] = 1;
    dp[0][1] = 1;
    dp[0][2] = 1;
    for (int i = 1; i < n; i++)
    {
        dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % 9901;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;
    }
    cout << (dp[n - 1][0] + dp[n - 1][1] + dp[n - 1][2]) % 9901 << "\n";
}