[백준 1309] 동물원 C++ (DP, 다차원)

다이나믹 프로그래밍으로 풀이가 가능한 대표적인 문제입니다.

일차원 배열을 사용하여 풀이할 수 있지만, 이차원 배열을 사용하여 풀이하는 방법도 존재합니다.

코드

#include <cstdio>
using namespace std;
const int mod = 9901;

int n;
int d[100010][4];

// d[n][m] = n은 2*n배열에 사자를 배치하는 경우의 수
//           m은 배치 방식(배치x, 왼쪽, 오른쪽)
int main(void)
{
    scanf("%d", &n);
    d[1][1] = 1; //배치 x
    d[1][2] = 1; //왼쪽 배치
    d[1][3] = 1; //오른쪽 배치

    for (int i = 2; i <= n; i++)
    {
        d[i][1] = d[i - 1][1] + d[i - 1][2] + d[i - 1][3];
        d[i][2] = d[i - 1][1] + d[i - 1][2];
        d[i][3] = d[i - 1][1] + d[i - 1][3];

        //9901로 나누기
        d[i][1] %= mod;
        d[i][2] %= mod;
        d[i][3] %= mod;
    }

    printf("%d\n", (d[n][1] + d[n][2] + d[n][3]) % mod);
}