[DP] 동물원 (1309)(C++)

https://www.acmicpc.net/problem/1309

1309번: 동물원

 

1. 문제 개요

 

2*N 배열에 사자를 가둘 때, 위 아래 양 옆으로 사자 붙어 있지 않게 하는 배치는 몇 가지인지 구하는 문제이다. 이 때, 가두어야하는 사자의 수는 정해져있지 않으며, 사자가 한 마리도 없는 경우도 하나의 경우의 수로 포함된다.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

처음에는 왜인지 백트랙킹 문제라고 생각했다.. 근데 DP로 풀으라는 말을 보고 다시 생각해보니 금방 풀렸다.

규칙은 다음과 같다.

N=1인 배열이 있다면 사자를 가두는 경우의 수는 다음과 같이 3가지일 것이다.

 

그 다음에, N=2인 배열의 경우의 수를 구하려 하면, N=1인 배열의 경우의 수에서 하나의 행을 추가하면 될 것이다.

그림을 보면 알 수 있듯이, 이전 행에 1이 포함되어 있는 경우는 각각 두 가지 경우의 수, 1이 포함되어 있지 않은 경우는 세 가지 경우의 수를 추가로 만들어낸다. 따라서 이는 2차원 배열 형태로 나타낼 수 있다.

	1	2	3	4
1 포함	2	4	10	24
1 포함 X	1	3	7	17

 

list[i][0] = list[i-1][0] + list[i-1][1]*2

list[i][1] = list[i-1][0] + list[i-1][1]

 

이렇게 두 가지의 점화식이 나오게 되고, 최종적으로 우리가 알고 싶은 N*2 배열의 경우의 수는 list[N][0] + list[N][1]이 된다.

 

 

4. 전체 코드

 

#include <algorithm>
#include <iostream>

using namespace std;

int list[2][100000];

int main(void) {
    int N;
    scanf("%d",&N);
    
    list[0][0] = 2;
    list[1][0] = 1;
    
    for(int i=1;i<N;i++) {
        list[0][i] = (list[0][i-1] + list[1][i-1]*2)%9901;
        list[1][i] = (list[0][i-1] + list[1][i-1])%9901;
    }
    
    printf("%d\n",(list[0][N-1]+list[1][N-1])%9901);
}

 

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!