[1309] 동물원

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

다른 분들은.. 도대체 어떻게 푸신건지.. 잘 이해가 안가더라구요...ㅎㅎ...

저는.. 좀 어렵게 푼듯 하네요... 다른분들은 1차원 dp인데 저는 2차원 dp라고 생각했습니다.

dp[N][3]으로 2차원 dp를 정의했고

N은 칸 수 뒤의 3은

0 = N번째 칸에 사자를 안넣는 경우

1 = 1번째 칸에 사자를 넣는 경우

2 = 2번쨰 칸에 사자를 넣는 경우

라고 생각하고 풀었습니다.

n칸에다가 사자를 안넣는다면

dp[n][0]은 dp[n - 1][0] + dp[n - 1][1] + dp[n - 2][2]입니다.

n칸에다가 사자를 안넣는 경우는 n - 1 칸에서 사자를 안넣는경우, 사자를 1칸에 넣는 경우, 2칸에 넣는경우 셋 다 가능하기 때문입니다.

n의 1칸에 사자를 넣는다면 n-1칸에서는 사자를 안넣거나 2칸에 넣는다면 n의 1칸에 사자를 넣을 수 있으므로 그 두개를 더합니다.

n의 2칸에서는 1칸과 동일하게 n - 1칸에 사자를 안넣는 경우, 1칸에 넣는 경우 두가지를 더합니다.

점화식은..

for(int i = 2; i <= n; i++)
{
    dp[i][0] = dp[i - 1][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];
}

입니다!

아래는 풀 코드입니다.

#include <cstdio>
#define MAX_SIZE 100001
 
int dp[MAX_SIZE][3];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i = 0; i < 3; i++) dp[1][i] = 1;
 
    for(int i = 2; i <= n; i++)
    {
        dp[i][0] = dp[i - 1][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];
 
        for(int j = 0; j < 3; j++) dp[i][j] %= 9901;
    }
    printf("%d\n", (dp[n][0] + dp[n][1] + dp[n][2])%9901);
 
    return 0;
}