(C++) - 백준(BOJ) 1309번 : 동물원

 

S[n]을 사자를 배치하는 경우의 수라고 정의한다.

S[n][0] : 사자 배치를 아무것도 안하는 것

S[n][1] : 사자 배치를 왼쪽에만 하는 것

S[n][2] : 사자 배치를 오른쪽에만 하는 것

s[i][0] = s[i-1][0] + s[i-1][1] + s[i-1][2], 아무것도 배치하지 않으므로 그 전 경우에서 모든 상황에 배치가 가능하다.
s[i][1] = s[i-1][0] + s[i-1][2], s[i-1][1]은 배치할 수 없으므로 더하지 않는다.
s[i][2] = s[i-1][0] + s[i-1][1], s[i-1][2]는 배치할 수 없으므로 더하지 않는다.

위 수식에서 미루어 보았을 때 사자의 배치를 가로 또는 세로 한칸 떨어진 상황에서는 하지 못하므로 각자의 상태에 따라 추가되는 경우의 수가 다르다.

 

#include <iostream>
#define ll long long
using namespace std;
ll n;
ll s[100001][3];
int main() {
    cin >> n;
    s[1][0] = 1;
    s[1][1] = 1;
    s[1][2] = 1;
 
    for (int i = 2; i <= n; i++)
    {
        s[i][0] = (s[i-1][0] + s[i-1][1] + s[i-1][2]) % 9901;
        s[i][1] = (s[i-1][0] + s[i-1][2]) % 9901;
        s[i][2] = (s[i-1][0] + s[i-1][1]) % 9901;
    }
    cout << (s[n][0] + s[n][1] + s[n][2]) % 9901;
}