[C++] 백준 1309번 동물원

 

1) 문제설명

백준 Online Judge 1309번 동물원

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

1309번: 동물원

 

2) 아이디어

처음에는 2차원 배열로 dp를 설정하여 마릿수 / n층으로 표를 그려 규칙을 찾으려고 했으나 규칙을 찾기가 매우 어려웠다.

따라서 이를 해결하기 위해 dp [n층][사자를 배치하지 않음/ 사자를 왼쪽에 배치/ 사자를 오른쪽에 배치]로 나누어서 생각하였다.

처음 dp [1][0] = 1층에 사자를 배치하지 않는 경우의 수는 = 1이다

마찬가지로 dp [1][1] = 1층에 사자를 왼쪽 배치할 경우의 수 = dp [1][2] = 1층에 사자를 오른쪽 배치할 경우의 수 = 1

이후 2층에 사자를 배치할 경우의 수를 구해본다면

dp [2][0] : 2층에 사자를 배치하지 않을 경우 1층에 사자를 배치하지 않거나, 왼쪽, 오른쪽 배치 상관없으므로

dp [2][0] = dp [1][0] + dp [1][1] + dp [1][2]

dp [2][1] : 2층에 사자를 왼쪽 배치할 경우 1층에 사자를 배치하지 않거나 오른쪽에만 배치해야 하므로

dp[2][1] = dp [1][0] + dp [1][2]

마찬가지로 dp [2][2] = dp [1][0] + dp [1][1]이 성립한다.

이를 토대로 코드를 작성한다

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
// dp[n][] : n층에 사자를 배치하는 경우의 수 
long long dp[100001][3];
int arr[1000001];
int main() {
	int n;
	cin >> n;
	dp[1][0] = 1; // 1층에 사자를 배치하지 않을때
	dp[1][1] = 1; // 1층에 사자를 왼쪽 배치
	dp[1][2] = 1; // 1층에 사자를 오른쪽 배치
	int sum = 3;
	for (int i = 2; i <= n; i++) {
		sum = 0;
		dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
		dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
		sum = (dp[i][0] + dp[i][1] + dp[i][2]) % 9901;
	}
	cout << sum;
	
}