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

문제

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

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

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

 

입력

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

 

출력

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

---

동적계획법을 이용한 문제

 

식을 때려맞춰서 풀어버려서

내가 생각한 풀이는 다음과 같다...

i - 1번째 줄이 X X일때

i번째 줄에 사자를 둘 수 있는 경우는 X X, X O, O X의 세가지이고

i - 1번째 줄이 O X 또는 X O일때

i번째 줄에 사자를 둘 수 있는 경우는 각각 X X, X O 또는 X X, O X 이다.

 

그래서 i를 1부터 늘여뜨려서 정리했을 때

 

lion[1] = 3

lion[2] = 1 * 3 + 2 * 2 = 7

lion[3] = 3 * 3 + 4 * 2 = 17

lion[4] = 7 * 3 + 10 * 2 = 41

.

.

 

어떠한 규칙을 찾았고, 그리하여 식을 정리했더니 다음과 같았다.

lion[i] = lion[i - 2] * 3 + (lion[i - 1] - lion[i - 2]) * 2

위의 식을 정리하면 다음과 같이 나온다

lion[i] = lion[i - 2] + lion[i - 1] * 2

 

코드

#include <cstdio>
#define MAX 100001
#define MOD 9901

int DP(int num);
int lion[MAX];

int main(void) {
    int N;
    scanf("%d", &N);

    printf("%d\n", DP(N));
    return 0;
}

int DP(int num) {
    lion[0] = 1;
    lion[1] = 3;
    
    for(int i = 2; i <= num; i++) {
        lion[i] = (lion[i - 2] + lion[i - 1] * 2) % MOD;
    }

    return lion[num];
}