[DP] BOJ 1309번 동물원 - 오답 노트

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

1309번: 동물원

- 문제파악

정수 n이 주어진다. 2*N 행렬이 있을때 0마리 부터 N 마리의 사자를 인접하지 않도록 놓는 경우의 수를 출력하라

 

- 나의 접근

이중배열은 생각했지만 나는 n이 1일 때 0마리부터 n마리를 넣는 배열로 생각했었다

그러면 시간복잡도가 최대 n*(n-1) 이므로 n이 10만이면 바로 시간초과 여기서 또 막혔다.

 

- 정답

사자를 몇마리를 넣을지가 아니라 이전에 넣었던 사자의 위치로 이전 값에 더하는 식으로 접근해야한다.

 

D[i][j] 에서

i 는 세로 길이

j 는 0 일때는 사자를 두지 않는 경우 1은 오른쪽 2는 왼쪽이다.

 

그렇다면 

D[i-1][0] (이전 칸에 사자를 두지 않는 경우)는 다음 칸에 왼쪽, 오른쪽, 두지 않아도 상관 없다.

D[i-1][1] (이전 칸에 사자를 오른쪽에 두는 경우)는 왼쪽 또는 두지 않는 경우 밖에 없다.

D[i-1][2] (이전 칸에 사자를 왼쪽에 두는 경우)는 오른쪽 또는 두지 않는 경우 밖에 없다.

 

위 경우를 점화식으로 표현하면 아래와 같다.

D[i][0] = D[i-1][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][0] + D[i-1][1] 

 

#include "bits/stdc++.h"

using namespace std;


int n;
unsigned long long D[100001][4];

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

	cin >> n;

	D[0][0] = 1;
	D[0][1] = 1;
	D[0][2] = 1;

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


	cout << ((D[n - 1][0] + D[n - 1][1] + D[n - 1][2]) % 9901);
	
}