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

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

1309번: 동물원

 

알고리즘 분류 : DP

푸는 과정

사자의 배치는, 각 행별로 없거나 앞의 행의 대각선에만 배치가 가능하다.

앞이 00이라면, 00 10 01 이 가능

앞이 10이라면 00,01

앞이 01이라면 00,10 이 가능 하다.

 

말하자면,

 

2*N칸의 우리에 사자를 배치할 수 있는 경우의 수는

 

N번째칸에 00이 가능한 경우의 수 + 01이 가능한 경우의수 + 10이 가능한 경우의 수인데,

각 경우를 

d[n][0] / d[n][1] / d[n][2] 이라고 하면

 

d[n][0] = d[n-1][0] + d[n-1][1] + d[n-1][2]

d[n][1] = d[n-1][0] + d[n-1][2] 

d[n][2] = d[n-1][0] + d[n-1][1] 

 

이다.

 

2*1 칸에서 가능한 경우는 00,01,10. 00,10,01 이 가능한 경우의 수가 각각 1,1,1 인 것이다.

2*2 칸에서 가능한 경우는 1+1+1,1+1,1+1 이다.

2*3칸에서 가능한 경우는 3+2+2, 3+2, 3+2 이다.

....

 

코드

#include <iostream>
#include <vector>
#define DIV 9901
#define MAX 100000+1
using namespace std;

int lions[MAX][3] = {0};

int main()
{
    int N,answer;
    cin >> N;
    lions[1][0] = 1;
    lions[1][1] = 1;
    lions[1][2] = 1;
    for(int i=2; i<=N; i++)
    {
        lions[i][0] = (lions[i-1][0] + lions[i-1][1] + lions[i-1][2]) % DIV;
        lions[i][1] = (lions[i-1][0] + lions[i-1][2]) % DIV;
        lions[i][2] = (lions[i-1][0] + lions[i-1][1]) % DIV;
    }
    answer = (lions[N][0] + lions[N][1] + lions[N][2]) % DIV;
    cout << answer;
}