[C++] 백준알고리즘 1309번 동물원 문제

문제

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

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

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

입력

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

출력

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

 

 

칸은 2*n 이므로

사자가 들어갈수있는방법은 

1. 전칸에 사자가없었을때

2. 전칸에 왼쪽에 사자가있었을때

3. 전칸에 오른쪽에 사자가있었을때

문제

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

 



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

 

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

 

입력

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

 

출력

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

 

 

 

 

 

칸은 2*n 이므로

 

사자가 들어갈수있는방법은 

 

1. 전칸에 사자가없었을때

 

2. 전칸에 왼쪽에 사자가있었을때

 

3. 전칸에 오른쪽에 사자가있었을때

 

이지만 계산해보면 2,3 의 값은같아진다

그러므로 점화식은 

F(N)=2*F(N-1)+F(N-2) 가 답이된다.

코드

#include <stdio.h>
int dp[100001][3];
int main()
{
    int N;
    int i;
    scanf("%d", &N);
    dp[0][0] = { 0 };
    dp[1][0] = dp[1][1] = dp[1][2] = 1;
    for (i = 2; i <= N+1; i++)
    {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
    }
    printf("%d", dp[N+1][0] % 9901);
}