[C++] 백준 1309 : 동물원

문제를 읽고 일단 어떤 경우의 수가 가능할 지 생각을 해보았다. 

 

n = 1일 때, 즉 우리가 2칸일 때에 3개의 경우의 수가 있음을 쉽게 생각해 낼 수 있다: 사자가 없을 때, 첫번째 칸에 사자가 있을 때, 두번째 칸에 사자가 있을 때 

 

n을 하나 늘리기 전에 현재 경우의 수가 어떠한 영향을 줄 수 있을 지 생각해보자. 

만약에 제일 밑 칸이 빈칸이라면 n이 하나 늘어났을 때에 현재 제일 밑 칸 아래에 새로 생길 칸의 구성은 3가지다: 빈 칸, 왼쪽 칸에 사자, 오른쪽 칸에 사자. (두 칸 모두 사자가 존재할 수는 없다)

하지만 제일 밑 칸 중 한 칸에 사자가 있다면 새로운 두 칸의 구성은 2가지가 가능하다: 빈 칸 그리고 제일 밑 칸에 있는 사자와 붙어있지 않는 쪽 칸에 사자

 

n이 늘어날 때마다 새로 더해지는 칸이 빈 칸인 경우는 n-1번째에 총 경우의 수만큼이다. 

맨 밑에 사자가 있는 경우는 (2*n-1번째 맨 밑이 빈칸인 경우) + (1*n-1번째 맨 밑에 사자가 있는 경우) 이다. 

 

 

 

위에 설명한 바를 그냥 생각한대로 짜면 아래와 같다. 

#include <iostream>

int main(){
    int n; // 1 <= n <= 100,000
    scanf("%d", &n);

    long empty = 1;
    long one = 2;
    long total = empty + one;
    for(int i=1; i<n; i++){
        one = (empty*2) + (one*1);
        empty = total;
        total = (one + empty) % 9901;
    }
    printf("%ld", total%9901);

    return 0;
}

 

하지만, 좀 더 생각하고 명료한 식을 도출해보았을 때는 아래와 같다. 

둘 다 테스트 케이스는 다 통과한다. 

 

#include <iostream>

int main(){
    int n; // 1 <= n <= 100,000
    scanf("%d", &n);

    int cases[100001];
    cases[0] = 3;
    cases[1] = 7;
    for(int i = 2; i<=n; i++){
        cases[i] = (cases[i-2] + (cases[i-1]*2))%9901;
    }
    
    printf("%d", cases[n-1]%9901);

    return 0;
}