[BOJ/백준 1309/C++] 동물원

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

1309번: 동물원

 

[문제 요약]

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

- 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 

- 이때 2 * N 배열에 사자를 배치하는 경우의 수를 구하여라.

- 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

- 정답은 9901로 나눈 나머지를 출력하라.

 

[문제 조건]

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

- 시간 제한 : 2초

- 메모리 제한 : 128MB

 

[문제 풀이]

문제에서 정답을 어떤 수로 나눈 나머지를 출력하라는 건 정답이 매우 크다는 걸 의미한다. 벌써부터 쫄린다.

 

문제를 읽어보고 한 번 생각을 해보면 딱히 떠오르는 방법이 DP말고는 떠오르지 않는다.

 

그래서 필자는 DP를 이용하여 문제를 접근하였다.

 

먼저 가로줄 한 줄에 배치할 수 있는 경우는 총 3가지이다. 왼쪽에 놓거나, 오른쪽에 놓거나 아니면 배치하지 않거나.

여기서 필자는 두 가지 경우의 수로 나누어 생각해봤다. 배치하지 않았을 때와 배치를 하나라도 했을 경우.

이 방법을 적용하여 표를 그리고 값들을 작성하면 아래와 같다.

일단, 예들들어 초록색 부분이 의미하는 건 N=2일때 2번째 칸에 사자를 배치하지 않았을때 경우의수는 총 3가지, 둘 중 한곳이라도 배치한다면 4가지 해서 총 7가지라는 의미이다.

 

여기서 표를 채우는 방법은 간단하다.

만약 N번째에 사자를 채우지 않는다는 것은 크기가 2 * (N-1)배열에 사자를 배치하는 경우의 수와 같을 것이다. 왜냐하면 배치하지 않는건 다른 제약을 받지 않으니.

 

그리고 N번째에 배치한다고 생각하면, 왼쪽 오른쪽 총 2가지 경우가 있다. 그리고 만약 N-1번째에 배치 하지 않았다면 왼쪽 오른쪽 둘 다 가능함으로 7x2 = 14.

 

그 다음 N-1번째에 사자가 배치되어 있을 경우 N-1번째에 따라서 N번째에 배치할 수 있음으로 N번째는 N-1번째에 따라가게 된다. 따라서 10개 추가 하면 10+14해서 총 24가지가 나온다.

 

정리하자면

 

DP[N][0] = DP[N-1][0] + DP[N-1][1]

DP[N][1] = DP[N-1][0] * 2 + DP[N-1][1]

해서 DP[N][0] + DP[N][1]이 정답이 될 것이다.

 

근데 식을 가만히 보고있자니 뭔가 정리를 할 수 있을 것 같다. MP[N]을 2 * N에 사자를 배치하는 수라고 다시 정의하면

DP[N][0] + DP[N][1] = 3 * DP[N-1][0] + 2 *  DP[N-1][1]

MP[N] = 2*MP[N-1] + MP[N-2]이다. ( 남은 DP[N-1][0]은 사실상 N-2일때의 값과 같긴 때문에 MP[N-2]로 표현 가능)

 

그래서 사실상 이 문제의 점화식은 MP[N] = 2*MP[N-1] + MP[N-2] 가 된다.

그리고 자료형을 unsigned long long과 값을 9901의 나머지로 저장을 해주면 정답이 된다.

 

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int N;
vector<unsigned long long> DP;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;
	DP.resize(N + 1);

	DP[0] = 3;
	DP[1] = 7;
	for (int i = 2; i <= N; i++)
	{
		DP[i] = (2 * DP[i - 1])%9901 + (DP[i - 2]%9901) % 9901;
	}
	cout << DP[N-1] % 9901;
}

 

굳