3806 : 동물원

안녕하세요! 오늘은 CodeUp에서 제공하는 문제 중 하나인 "동물원 사자 배치하기" 문제에 대한 해결 코드와 설명하는 블로그를 작성하려고 합니다. 이 문제는 주어진 동물원 우리 크기에 따라 사자를 배치하는 경우의 수를 구하는 것이 목표입니다. 아래에서 코드와 함께 문제를 설명하고 해결하는 방법에 대해 알아보겠습니다.

문제 설명

어떤 동물원에 가로로 두 칸, 세로로 N칸인 우리가 있습니다. 이 동물원에는 사자들이 살고 있는데, 사자들을 우리에 가둘 때 가로로나 세로로 붙어있게 배치할 수는 없습니다. 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있습니다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주세요. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 치자고 가정합니다.

입력

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

출력

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

입력 예시

Copy code
4


출력 예시

Copy code
41


문제 해결 방법

이 문제를 해결하기 위해 재귀 함수를 활용하는 방법이 적합합니다. 문제에서 요구하는 경우의 수를 구하기 위해 재귀 함수를 호출하고, 가능한 모든 배치를 탐색합니다. 이때, 배치된 사자가 서로 충돌하지 않도록 규칙을 확인하여 올바른 배치를 찾아야 합니다.

코드 설명

아래는 문제를 해결하는 C 코드입니다.

c
Copy code
#include <stdio.h>

long long int memo[100001] = {0};

long long int recur(int a){
    if(a == 0){
        memo[a] = 1;
        return 1;
    }
    if(a == 1){
        memo[a] = 3;
        return 3;
    }
    if(a == 2){
        memo[a] = 7;
        return 7;
    }
    if(memo[a] != 0){
        return memo[a];    
    }
    else{
        return memo[a] = (recur(a-1) * 2 + recur(a-2)) % 9901;
    }
}

int main(){
    int a;
    scanf("%d", &a);
    long long int result = recur(a);
    printf("%lld\n", result);
    return 0;
}


위 코드는 입력으로 받은 우리의 크기에 따라 재귀 함수 recur를 호출하여 사자를 배치하는 경우의 수를 구합니다.

함수 recur는 크기 a에 따라 사자를 배치하는 경우의 수를 반환합니다. 이때, 이전에 구한 경우의 수를 저장하기 위한 memo 배열을 활용하여 중복 계산을 피합니다.

주어진 크기 a에 따라 경우의 수를 계산하는 규칙은 다음과 같습니다:

a = 0일 때, 사자를 배치하지 않는 경우 1가지.
a = 1일 때, 사자를 한 칸에 배치하는 경우 3가지.
a = 2일 때, 사자를 두 칸에 배치하는 경우 7가지.
a > 2일 때, 사자를 배치하는 경우의 수는 이전 두 개의 경우의 수를 합친 것과 동일합니다. 이전 경우의 수는 memo 배열을 활용하여 저장하고, 경우의 수는 9901로 나눈 나머지를 저장합니다. (정답 출력 시 9901로 나눈 나머지를 출력합니다.)

위 코드를 실행하면 입력으로 주어진 우리의 크기에 따른 사자 배치의 경우의 수를 출력합니다.

이렇게 해서 동물원 사자 배치하기 문제를 해결하는 방법에 대해 알아보았습니다. 문제 해결에는 재귀 함수와 메모이제이션을 활용하여 경우의 수를 탐색하고 중복 계산을 피하는 방식을 사용했습니다. 문제를 해결하는 데에는 문제를 이해하고 규칙을 파악하여 적절한 알고리즘을 설계하는 것이 중요합니다. 감사합니다!