[백준] 동물원 1309번 (c++)

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

1309번: 동물원

풀이 방법

가로로도 세로로도 붙어 있으면 안되기 때문에 

경우의 수를 3가지로 나누었다.

dp_l[i] = i 번째 줄에 왼쪽에 사자가 있고 오른엔 사자가 없는 경우

dp_r[i] = i 번째 줄에 오른쪽에 사자가 있고 왼쪽엔 사자가 없는 경우

dp_z[i] = i 번째 줄에 왼쪽 오른쪽 둘다 사자가 없는 경우

점화식 은

dp_l[i] = dp_z[i] + dp_r[i];

dp_r[i] = dp_z[i] + dp_l[i];

dp_z[i] = dp_z[i] + dp_l[i] + dp_r[i] 

로 포현하면 가로로 세로로 붙어 있는 경우가 없다.

그리고 정답은 dp_l[n] + dp_r[n] + dp_z[n]을 해주면 된다.

#include <bits/stdc++.h>
using namespace std;

int dp_l[100001], dp_r[100001], dp_z[100001];
int n;
#define MOD 9901

int main() {
    dp_l[1] = 1;
    dp_r[1] = 1;
    dp_z[1] = 1;
    dp_l[2] = 2;
    dp_r[2] = 2;
    dp_z[2] = 3;
    cin >> n;
    for (int i = 3;i <= n;i++) {
        dp_l[i] = (dp_z[i-1] + dp_r[i-1]) % MOD;
        dp_r[i] = (dp_z[i-1] + dp_l[i-1]) % MOD;
        dp_z[i] = (dp_z[i-1] + dp_l[i-1] + dp_r[i-1]) % MOD;
    }
    int ans = (dp_l[n] + dp_r[n] + dp_z[n]) % MOD;
    cout << ans;

    return 0;
}