[백준 BOJ 1309번] 동물원 (C / C++ ) [DP, 다이나믹 프로그래밍]

1309번: 동물원 (acmicpc.net)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128MB	13927	7115	5606	49.180%

문제

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

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

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

입력

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

출력

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

예제 입력 1

4

예제 출력 1

41

풀이

사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다는 것에 주목을 하여 직접 계산을 해 보면

N이 1일 때부터 4일 때까지 각각 3,7,17,41 가지의 경우의 수가 나온다.

이때 규칙을 찾아보면 N의 값은 (N-1의 경우의 수) * 2 + (N-2의 경우의 수)라는 규칙이 생기는 것을 알 수 있고, 이 것을 점화식으로 다시 풀어보면,

dp[N]=dp[N-1]*2 + dp[N-2]

라는 점화식이 나오는 것을 알 수 있다.

N의 경우의 수는 위 점화식으로 계산한 값을 9901로 나눈 나머지를 저장하면 된다.

코드

// 동물원
// 다이나믹 프로그래밍
#include <iostream>
int D[100001]={1,3};
int main(){
    int N;
    std::cin>>N;
    for(int i=2;i<=N;i++)
        D[i]=(D[i-1]*2+D[i-2])%9901;
    std::cout<<D[N];
}

 

1309번: 동물원 (acmicpc.net)

1309번: 동물원