[C/C++] 백준 - 1309번 : 동물원

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

1309번: 동물원

문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

 

문제를 읽어보면 바로 DP문제라는 것을 알 수 있다.

그럼 어떻게 메모이제이션으로 해결할 수 있을까?

 

일단 경우의 수를 나누어보자.

N번째 칸에 사자들을 놓을 수 있는 경우의 수는

   첫째, 아무 사자도 놓지않는다

   둘째, 왼쪽 칸에 사자를 놓는다

   셋째, 오른쪽 칸에 사자를 놓는다

이렇게 N번째 칸에 사자를 놓을 수 있는 경우의 수는 3가지가 존재한다.

-> 위 설명을 배열로 나타내면 DP[MAX_INDEX][3]이 된다.

DP[i][0] -> i번째 칸에 아무 사자도 놓지 않는 경우의 수

DP[i][1] -> i번째 칸에 왼쪽 사자만 놓은 경우

DP[i][2] -> i번째 칸에 오른쪽 사자만 놓은 경우

 

그 다음에 N+1번째 칸에 사자를 놓을 수 있는 경우의 수를 생각해보자.

   첫째, 아무 사자도 놓지 않는다. (위 칸의 사자우리에 영향x)

   둘째, 왼쪽 칸에 사자를 놓는다 -> 왼쪽 칸에 사자를 놓으려면 가로세로 인접한 칸에 사자가 존재하면 안되므로

          (위 칸에 아무 사자도 놓지 않은 경우의 수 + 오른쪽 칸에 사자가 놓여있는 경우의 수) 가 된다.

   셋째, 오른쪽 칸에 사자를 놓는다 -> 위 설명과 동일하므로

          (위 칸에 아무 사자도 놓지 않은 경우의 수 + 왼쪽 칸에 사자가 놓여있는 경우의 수) 가 된다.

 

그러므로 점화식은 초기식이

DP[0][0] = DP[0][1] = DP[0][2] = 1이 된다.

그리고 다음 식은

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

가 되고 모든 경우의 수를 더해야만 2 x N칸 우리의 사자를 놓을 수 있는 모든 경우의 수가 된다.

 

< 코드 >

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#define INF 987654321
#define Mod 9901
#define CUNLINK ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define ll long long
#define ENDL cout << endl
#define endl '\n'

using namespace std;

int dp[100001][3];

int main() {
	CUNLINK;
	int n; cin >> n;
	dp[0][0] = 1;
	dp[0][1] = 1;
	dp[0][2] = 1;
	for (int i = 1; i < n; i++) {
		dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % Mod;
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % Mod;
		dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % Mod;
	}
	int answer = (dp[n-1][0] + dp[n-1][1] + dp[n-1][2]) % Mod;
	cout << answer;

	return 0;
}