[BOJ] 1309번 | 동물원 (C++)

🔗문제 보러가기

1309번: 동물원

 

🧑🏻‍💻풀이 과정

Dynamic Programming 문제입니다. \( n = 1\), \( n = 2\), ... 일 때의 경우의 수를 한 번 점검해보면, 패턴이 보이는 것을 알 수 있습니다.

/*
	- 어떤 한 행에 있어서 가질 수 있는 경우의 수는 다음과 같은 3가지
	[][], [o][], [][o]
*/

        [][]	[o][]	[][o]
n = 1 :  1        1       1
n = 2 :  3        2       2
n = 3 :  7        5       5
n = 4 : 17       12      12
...

• [ ][ ]의 경우의 수는 n - 1번째의 [ ][ ] + [o][ ] + [ ][o] 값입니다.
• [o][ ]과 [ ][o]의 경우의 수는 n - 1번째의 [ ][ ] + [o][ ] (또는 [ ][o]) 값입니다.
• 따라서, n번째의 모든 경우의 수는 n번째의 [ ][ ] + [o][ ] + [ ][o] 값입니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
using namespace std;
const int DIVISOR = 9901;

int main()
{
	ios::sync_with_stdio(false);
	cout.tie(NULL); cin.tie(NULL);

	int N;
	cin >> N;

	int nothing = 1, existOne = 1;
	for (int i = 1; i < N; i++)
	{
		int temp = existOne;
		existOne = (existOne + nothing) % DIVISOR;
		nothing = (nothing + temp * 2) % DIVISOR;
	}

	cout << (nothing + existOne * 2) % DIVISOR;
	return 0;
}