Baekjoon1309-동물원

백준 사이트 1309 - 동물원 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

DP문제입니다.
백준에서는 Sliver1의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 규칙을 찾기위해 공책으로 n이 0, 1, 2, 3, 4 일 때를 직접 구해보았습니다.
• 규칙이 눈에 보이지 않았고, 실제로 계산한 n이 3일때가 틀려서 머리를 싸매고 있었던 중.. 포기하고 질문을 봤습니다.
• 규칙으로는 DP[n] = DP[n-2] + DP[n-1] * 2 라는 규칙이 있지만 봐도 왜그런지 이해 안되었습니다.
• 경우 3가지를 나눠 DP를 계산하는 방법을 보고 이해했습니다.
  • 경우1은 현재 줄에 사자 배치를 안할 때 입니다.(윗줄에 왼쪽에 사자 있는 경우의 수 + 오른쪽에 사자 있는 경우의 수) -> 어디에 사자가오든 상관 없으므로
  • 경우2는 현재 줄 왼쪽에 사자를 배치할 경우입니다.(윗줄에 사자가 없는 경우 + 오른쪽에 사자가 있는 경우)
  • 경우3은 현재 줄 오른쪽에 사자를 배치할 경우입니다.( 윗줄에 사자가 없는 경우 + 왼쪽에 사자가 있는 경우)

---

5. code

#include<iostream>

using namespace std;
const int MAX = 100002;
int DP[MAX][4] = { 0, };

void printDP(int n)
{
	for (int i = 0; i <= n; ++i)
	{
		for (int j = 0; j < 3; ++j)
			cout << DP[i][j] << " ";
		cout << '\n';
	}
}

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

	int n;
	cin >> n;
	DP[1][0] = 1;
	DP[1][1] = 1;
	DP[1][2] = 1;
	for (int i = 2; i <= n; ++i)
	{
		//경우 1 미배치 하는 경우
		DP[i][0] = (DP[i - 1][0] + DP[i - 1][1] + DP[i - 1][2]) % 9901;
		//경우 2 왼쪽 칸에 사자를 배치할 경우
		DP[i][1] = (DP[i - 1][0] + DP[i - 1][2]) % 9901;
		//경우 3 오른쪽 칸에 사자를 배치할 경우
		DP[i][2] = (DP[i - 1][0] + DP[i - 1][1]) % 9901;
	}
	cout << (DP[n][0] + DP[n][1] + DP[n][2])%9901;
}

---

6. 후기

규칙으로 푸는 점화식 증명.. 난 이렇게 못품.. https://www.acmicpc.net/board/view/10263