190704 BOJ 1309 동물원

다이나믹 프로그래밍

1. 사자를 배치하는 경우의 수는 왼쪽, 오른쪽, 배치 안하기 3가지 경우의 수

2. 바로 윗칸에 배치된 경우는 배치할 수 없다.

3.

왼쪽에 배치하는 경우의 수 = 직전 윗 칸의 오른쪽에 배치하는 경우의 수 + 직전에 배치 안하는 경우의 수

오른쪽에 배치하는 경우의 수 = 직전 윗 칸의 왼쪽에 배치하는 경우의 수 + 직전에 배치 안하는 경우의 수

배치 안하는 경우의 수는 제약이 없으므로 직전 윗 칸의 왼쪽, 오른쪽, 배치 안하는 경우의 수를 합하면 된다.

식을 세워보면

D[100001][3] : D[행번호][왼쪽, 오른쪽, 배치x]

D[i][0] = D[i - 1][1] + D[i - 1][2] : i행의 왼쪽에 배치하는 경우의 수 = i - 1행의 오른쪽 배치 + i - 1행의 배치x

D[i][1] = D[i - 1][0] + D[i - 1][2] : i행의 오른쪽에 배치하는 경우의 수 = i - 1행의 왼쪽 배치 + i - 1행의 배치x

D[i][2] = D[i - 1][0] + D[i - 1][1] + D[i - 1][2] : i행의 배치x = i - 1 행의 (왼쪽 + 오른쪽 + 배치x)

소스 코드

#include <iostream>
#define ll long long
#define un unsigned
#define FOR(i,a,b) for(int i = a; i < b; i++)
using namespace std;
int N;
un ll D[100001][3];
int main() {
    cin >> N;
    FOR(i, 0, 3) D[0][i] = 1;
    FOR(i, 1, N) {
        D[i][0] = (D[i - 1][1] + D[i - 1][2]) % 9901;
        D[i][1] = (D[i - 1][0] + D[i - 1][2]) % 9901;
        D[i][2] = (D[i - 1][0] + D[i - 1][1] + D[i - 1][2]) % 9901;
    }
    cout << (D[N - 1][0] + D[N - 1][1] + D[N - 1][2]) % 9901;
}