1309. 동물원

점화식

• 점화식 조건식
  1) 현재열에서 왼쪽에 사자를 놓았을 경우,
  -> 0번인덱스로 지정하자.
  2) 현재열에서 오른쪽에 사자를 놓았을 경우,
  -> 1번 인덱스로 지정하자.
  3) 추가적으로 사자를 한마리도 배치하지 않았을 경우가 있음.
  -> 2번 인덱스로 지정하자.

• 점화식 d[i][j]
  : i번째 열, j행에 사자가 올 수 있는 모든 경우의 수

-> 최종적으로는 d[n][0] + d[n][1] + d[n][2] 를 구해야 함.

알아야 할점.

int d[100001][3] : 10만 * 3을 지역변수 했더니
스택오버플로우가 발생함.

• 지역변수는 크기가 크지 않으므로, 동적할당 하거나, 전역변수로 처리하자.

코드

#include <iostream>
using namespace std;
#include <vector>
#include <string>
int d[100001][3];
//14:29
int main()
{

	//d[i][0] = d[i - 1][1] : i번재 열의 왼쪽에 사자를 놓았을 때 
	//d[i][1] = d[i - 1][0] 
	//: i번재 열의 오른쪽에 사자를 놓았을 때 
	//사자를 배치하지 않을 경우도 있음. 

	// 0을 왼쪽 배치 , 1을 오른쪽 배치, 2를 사자 안놓았을 경우
	//d[i][0] = d[i - 1][1] + d[i - 1][2]
	//d[i][1] = d[i - 1][0] + d[i - 1][2]
	//d[i][2] = d[i - 1][1] + d[i - 1][2] + d[i - 1][0]
	// 배치안했을 경우는 윗열이 어떻게 되어있는 상관 없음. 

	int n;
	cin >> n;

	const int fix = 9901;

	// 초기값 설정하는 방법. 

	// 첫번째 열에서는 어떻게 초기값 설정할 것인가? 
	d[0][0] = 1;	d[0][1] = 1;	d[0][2] = 1;
	
	//arr[1][0] = 1 + 1; 2
	//arr[1][1] = 1 + 1; 2
	//arr[1][2] = 1 + 1 + 1; 3	
	//arr[2][0] = d[1][1] + d[1][2] -> 5
 	//arr[2][1] = d[1][0] + d[1][2] -> 5
	//arr[2][2] = d[1][0] + d[1][1] + d[1][2] -> 7
	//arr[3][0] = d[2][1] + d[2][2] -> 12
	//arr[3][1] = d[2][0] + d[2][2] -> 12
	//arr[3][2] = d[2][0] + d[2][1] + d[1][2] -> 17
	//arr[4][0] = d[3][1] + d[3][2] -> 29
	//arr[4][1] = d[3][0] + d[3][2] -> 29
	//arr[4][2] = d[3][0] + d[3][1] + d[1][2] -> 41

	for (int i = 1; i < n; ++i)
	{
		d[i][0] = (d[i - 1][1] + d[i - 1][2]) % fix;
		d[i][1] = (d[i - 1][0] + d[i - 1][2]) % fix;
		d[i][2] = (d[i - 1][1] + d[i - 1][2] + d[i - 1][0]) % fix;
		//cout << d[i][0] << " " << d[i][1] << " " << d[i][2];

	}

	//cout << d[n - 1][0] << " " << d[n - 1][1] << " " 
	//	<< d[n - 1][2];
	cout << (d[n - 1][0] + d[n - 1][1] + d[n - 1][2]) % fix;
}