[백준][BOJ][C++][1309번] 동물원

문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

코드

dfs를 이용하여 문제를 풀다가 계속 안풀려서 구글링을 통해 dp로 풀어야한다는 것을 알게되었습니다. 참고한 주소와 코드 올려드립니다.

#include <iostream>
 
using namespace std;
 
 
 
const int MAX = 100000;
 
const int MOD = 9901;
 
 
 
int N;
 
int cache[3][MAX + 1]; //0: 없다, 1: 왼쪽에 있다, 2: 오른쪽에 있다
 
 
 
int Lion(void)
 
{
 
        //첫 번째 줄에 사자가 없을 수도, 왼쪽에 있을 수도, 오른쪽에 있을 수도 있다
 
        cache[0][1] = cache[1][1] = cache[2][1] = 1;
 
 
 
        for (int i = 2; i <= N; i++)
 
        {
 
               //전 줄의 배치와 상관없이 사자가 없을 수 있다
 
               cache[0][i] = (cache[0][i - 1] + cache[1][i - 1] + cache[2][i - 1]) % MOD;
 
               //전 줄에 없거나 오른쪽에 있었다면 왼쪽 배치 가능
 
               cache[1][i] = (cache[0][i - 1] + cache[2][i - 1]) % MOD;
 
               //전 줄에 없거나 왼쪽에 있었다면 오른쪽 배치 가능
 
               cache[2][i] = (cache[0][i - 1] + cache[1][i - 1]) % MOD;
 
        }
 
        return (cache[0][N] + cache[1][N] + cache[2][N]) % MOD;
 
}
 
 
 
int main(void)
 
{
 
        cin >> N;
 
        if (N<1 || N>MAX)
 
               exit(-1);
 
 
 
        cout << Lion() << endl;
 
        return 0;
 
}
 
 
 
출처: https://jaimemin.tistory.com/437 [꾸준함]