백준 1309 동물원

www.acmicpc.net/problem/1309

1309번: 동물원

 

#include <iostream>


#define MAX 100001
using namespace std;

int arr[MAX][3];

int main()
{


	arr[0][0] = 1; arr[0][1] = 1; arr[0][2] = 1;
	//각각 n줄 없, 왼없, 우없

	int n;
	cin >> n;

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

}

뭔가 생각하기 힘든 점화식이라 구현은 쉽지만 점화식을 찾는게 꽤 어려웠다

사실 얻어걸린 느낌으로 2X1-->2X2 -->2X3 로 모든 가능성을 열어서 

1.n번째 줄에 사자가 없을때

2.n번째 줄 왼쪽에 사자가 없을때

3.n번째 줄 오른쪽에 사자가 없을때

이렇게 나눠서 값을 더해나가니 규칙이 보였다

 

초기값으로 1 1 1 을 입력해 2X1인 경우 1줄에 사자가 없을때=1, 1줄왼 사자 없을때=1, 1줄오 사자 없을때=1;

부터 생각해 본다면 이해할 수 있을것이다

 

처음에 9901을 나누는게 마지막 ans에서 나누었다가 안으로 옮겨보고, 안으로 옮긴 뒤 ans에서도 나눠야 하는 이유는 모르겠지만...