[백준 1309] 동물원

문제출처: https://www.acmicpc.net/problem/1309

문제

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

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

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

입력

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

출력

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

풀이

이 문제를 dp로 풀어야겠다고 생각한분들 대단합니다.. 단순히 배열에 값 넣어서 규칙에맞게 푸는줄알았는데 절대안되더군요 그리고 규칙을 찾으려해도 이미 보기에서 4일때 41이라서 직접규칙을 찾을 엄두도안났네요.. 그래서 dp로 답을구한분들의 풀이를 참고하였습니다. dp인걸 알고나서는 dp연산을위한 배열선언 -> 초기값 설정 ,, 이 두 가지가 기본이잖아요? 어려웠던 부분은 dp[n][2]가 아닌 dp[n][3]으로 선언해야한다는 것입니다.

초기값설정을 위해 규칙을 알아봅시다. n=1일때, 총3가지경우가 나옵니다.(호랑이가 없을 때, 왼쪽에 호랑이 있을 떄, 오른쪽에 있을 때) 각각의 경우를 1로(다 가능한 경우이므로 0이아닌 참값으로설정) 초기화 하고 n=2일떄,n=3일떄.... 의 경우의수를 구하면됩니다. 위에서 언급한 3가지의 케이스를 이용하여 각각의 경우에 대해 가능한 경우의수를 담아야합니다. dp배열을 선언하는 것과 이 연산의 식 세우기가 어렵습니다.

결론적으로, dp[n][0]+dp[n][1]+dp[n][2]는  2*n공간에서 호랑이를 배열할 수 있는(호랑이가없는경우도 하나의경우로포함됨) 모든경우의 수 입니다.

코드

#include<iostream>
using namespace std;
int dp[100001][3];
//arr[x][0]=x층 아무도없을 떄
//arr[x][1]=x층 왼쪽에 호랑이O
//arr[x][2]=x층 오른쪽에 호랑이O
int main()
{
	int n;
	cin >> n;
	//n=1일때 ==초기값설정
	//n=1일때 3가지경우이므로 각 경우 1로설정
	dp[1][0] = dp[1][1] = dp[1][2] = 1;
	for (int i = 2; i <= n; i++)
	{
		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;
	}
	cout << (dp[n][0] + dp[n][1] + dp[n][2]) % 9901 << endl;
}

결과