[BOJ] 1309. 동물원 (dp)

Silver I

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

1309번: 동물원

 

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

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

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

 

input:

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

output:

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

 

---

Idea :

• DP 문제
• 규칙 찾기
  • 가로와 세로로 붙어 있게 배치할 수 없음 
    1.  이전 줄에 배치된 사자가 없을 경우,그 다음 줄에는 어느 위치든 배치할 수 있음
    2. 이전 줄에 배치된 사자가 있을 경우, 그 다음 줄에는 대각선 위치에만 배치할 수 있음
  • 한 줄에 대해 3가지 경우 가능
    1.  아무것도 배치하지 않는 경우
    2. 이전 줄에 배치된 사자가 없는 경우 = 왼쪽, 오른쪽 어느 칸이든 배치 가능
    3. 이전 줄에 배치된 사자가 있는 경우 = 이전 줄에 배치된 곳의 대각선에만 배치 가능
  • dp[i] = (i 번째 줄에 배치하지 않는 경우) + (이전 줄에 배치된 사자가 없는 경우) + (이전 줄에 배치된 사자가 있는 경우)                     = dp[i-1] + ( dp[i-2] * 2 ) + ( dp[i-1] - dp[i-2] )
             = dp[i-1] * 2 + dp[i-2]

Code :   

#include <iostream>

using namespace std;

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

	// freopen("input.txt", "rt", stdin);

	/* input */
	int N;
	cin >> N;

	/* solve */
	long dp_2 = 1, dp_1 = 3;
	long cur = dp_1;

	for (int i=2; i<=N; i++) {
		cur = (dp_1 * 2 + dp_2) % 9901;
		dp_2 = dp_1;
		dp_1 = cur;
	}

	/* print answer */
	cout << cur << "\n";
}

 

---

Result : 

메모리: 2020 KB,  시간: 0 ms

 

Review :