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

 

다이나믹 프로그래밍 문제입니다.

 

2*n개의 우리가 있을 때

사자가 서로 이웃하지 않고 있을 수 있는 

경우의 수를 찾는 문제입니다.

여기서 사자의 수는 주어지지 않습니다.

 

첫번째 우리의 경우

1. 사자 X

2. X 사자

3. X X

3가지 경우가 있습니다.

 

두번째 우리의 경우는

1번의 경우 첫번째 우리의 경우에서 오른쪽에 사자가 있거나 양쪽 전부 없는 경우 사자를 배치 할 수 있습니다.

2번의 경우 첫번째 우리의 경우에서 왼쪽에 사자가 있거나 양쪽 전부 없는 경우 사자를 배치 할 수 있습니다.

3번의 경우 첫번째 우리의 경우에서 3가지 경우 모두 배치할 수 있습니다.

 

이를 코드로 옮겨 보면

for (int i = 2; i <= n; ++i) {
	DP[0][i] = (DP[1][i - 1] + DP[2][i - 1]);
 	DP[1][i] = (DP[0][i - 1] + DP[2][i - 1]);
 	DP[2][i] = (DP[0][i - 1] + DP[1][i - 1] + DP[2][i - 1]);
}

이렇게 나타낼 수 있습니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int DP[3][100010];

int main(int argc, char *argv[])
{
   int n;
   int sum = 0;
   cin >> n;

   for (int i = 0; i < 100010; ++i) {
      DP[0][i] = 0;
      DP[1][i] = 0;
      DP[2][i] = 0;
   }

   DP[0][1] = 1;
   DP[1][1] = 1;
   DP[2][1] = 1;

   for (int i = 2; i <= n; ++i) {
      DP[0][i] = (DP[1][i - 1] + DP[2][i - 1]) % 9901;
      DP[1][i] = (DP[0][i - 1] + DP[2][i - 1]) % 9901;
      DP[2][i] = (DP[0][i - 1] + DP[1][i - 1] + DP[2][i - 1]) % 9901;
   }
   
   sum = (DP[0][n] + DP[1][n] + DP[2][n]) % 9901;
   cout << sum;

   return 0;
}