BOJ 1309 동물원(C++)

동물원 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2044	1043	848	50.267%

문제

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

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

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

입력

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

출력

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

예제 입력 

4

예제 출력 

41

힌트

출처

• 문제의 오타를 찾은 사람: joon8409
• 문제를 만든 사람: xhark

알고리즘 분류

• 다이나믹 프로그래밍

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include    <cstdio> #pragma warning (disable : 4996) #define div 9901 int A[111111][4]; int main() {     int n;     scanf("%d", &n);     A[1][0] = 1; //00     A[1][1] = 1; //01     A[1][2] = 1; //10       for (int i = 2; i <= n; ++i)     {         A[i][0] = (A[i - 1][0] + A[i - 1][1] + A[i - 1][2]) % div;         A[i][1] = (A[i - 1][0] + A[i - 1][2]) % div;         A[i][2] = (A[i - 1][0] + A[i - 1][1]) % div;     }       printf("%d", (A[n][0] + A[n][1] + A[n][2]) % div);         return 0; }

다이나믹 프로그래밍인데 약간 어려운 문제였다. 

점화식 세우기가 처음에는 애매... 

딱 보기에 1차원으로는 안끝날 것 같아서 2차원으로 생각해봤는데 상당히 어려웠다. 

A[N]이 N칸일 경우 모든 방법인것은 알겠는데

A[N][M]의 M을 무엇으로 설정해야 할지 감이 안잡혔다. 

처음에는 모든 방법의 수를 실제로 그려봤는데 뭔가 공식이 나올 것 같으면서도 안나오고... 

방법은

M을 4가지 케이스로 나누는 것이었다. (사실상 3가지 케이스)

N번째 칸에 사자가 들어갈 수 있는 경우의 수는 

1. 둘다 들어가지 않는다.

2. 왼쪽에 들어간다.

3. 오른쪽에 들어간다

4. 둘다 들어간다. 

이므로 총 3가지 

여기까지만 생각해보면 점화식은 간단히 나온다. 

안들어가는 경우의 수는 이전 우리에서 왼쪽에 들어가던 오른쪽에 들어가던 모두 가능하므로 아래와 같다.

D[i][00] = D[i-1][00] + D[i-1][10] + D[i-1][01] (이진수로 표현했을 경우..) 

왼쪽 또는 오른쪽에 들어가는 경우의 수는 바로위의 우리가 동일한 방향에 들어가있으면 안된다. 

(위에 우리에서 사자를 왼쪽에 넣었을 경우엔 해당 우리에서 왼쪽에 넣을 수 없음.)

D[i][01] = D[i-1][00] + D[i-1][10]

D[i][10] = D[i-1][00] + D[i-1][01]