[백준][DP] 동물원

1. 문제 주소

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

1309번: 동물원

2. 문제

N번째 행에서 사자가 아무 데도 없는 경우, 첫 번째 열에 있는 경우, 두 번째 열에 있는 경우의 수를 2차원 배열로 나타내면 쉽게 풀 수 있다.

3. 소스코드

#include <iostream>
using namespace std;
int dp[100001][3];
 
int main() {
    int n;
    cin >> n;
 
    dp[1][0] = 1;
    dp[1][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]) % 9901;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
    }
    cout << (dp[n][0] + dp[n][1] + dp[n][2]) % 9901 << '\n';
    return 0;
}