[c++] BOJ 1309번 :: 동물원

동물원

문제

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

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

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

입력

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

출력

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

예제 입력 1

4

예제 출력 1

41

나의 답

코드

N 입력 받기
sum = 1+2N (0마리, 1마리 경우)
for(i:2마리~N마리) // N
    sum+=CageCal(i,2N)

CageCal(n,size): // n: 몇마리 size: 우리 size
    tmp
    if(n==1)
        return size
    if(size가 홀수)
        return CageCal(n,size+1)-CageCal(n-1,size-2)
    for(i:0~size-2n+1) // 짝수만
        tmp+=2*CageCal(n-1,size-(i+3))
    return tmp

=> 시간 초과

=> 테스트 케이스 얻기

#include <iostream>

using namespace std;
int N;
int result[100001] = { 1,3 };

int main() {
    cin >> N;
    for (int i = 2; i <= N; i++) {
        result[i] = (result[i - 1] * 2 + result[i - 2])%9901;
    }
    cout << result[N]; // 여기서 나누면 오류
}

=> 규칙을 찾아서 점화식으로 대체하였다.

테스트 케이스

1=>3
2=>7
3=>17
4=>41
30000 => 3066
50000 => 2404
100000 => 8379

다른 답

규칙은 찾았지만 저렇게 되는 이유를 깨닫지 못했는데, 아래의 블로그에 잘 설명되어있다.

http://wookje.dance/2017/08/05/boj-1309-%EB%8F%99%EB%AC%BC%EC%9B%90/

다른 경우의 수로 나눈 방법도 있다.

http://isukorea.com/blog/home/waylight3/77