[ 백준 1309 ] 동물원 (C++)

백준의 동물원(1309) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 동물원에 동물을 가둬야 하는데, 가로 세로로 인접하게는 가둘 수 없을 때, 사자를 배치해야 하는 경우의 수를

   출력하는 문제이다.

   먼저 본인은 이 문제에서 경우의 수를 저장하기 위해서 DP[][] 2차원 배열을 사용하였다.

   DP[a][b] = c( 0 ~ b ~ 3) 의 의미는 "a번 줄에, b번에 사자를 배치했을 때 경우의 수는 c개 입니다." 이다.

   여기서 b는 3칸만 할당해줬으며 3칸의 의미는 0일 때는 그 줄에 사자를 배치 안했을 경우, 1일 때의 의미는

   그 줄에 왼쪽칸에 사자를 배치했을 경우, 2일 때는 그 줄에 사자를 오른쪽 칸에 배치했을 경우를 의미한다.

  

   그렇다면, 작은 값들로 부터 문제를 어떻게 풀어나가야 할지, 점화식을 어떻게 구할지 한번 생각해보자.

   N = 1 이라면 정답은 무엇일까??

   정답은 3이다. 왜냐하면 2x1의 칸에서 사자를 배치안하는 경우 1가지, 왼쪽칸에 사자를 배치하는 경우 1가지,

   오른쪽칸에 사자를 배치하는 경우 1가지 총 3가지가 된다.

   즉, DP[1][0] = DP[1][1] = DP[1][2] = 1이 된다. 이 식은 초기값으로 사용이 된다.

   그렇다면 N = 2일 때를 생각해보자. 이제는, 직관적인 값이 아니라 어떠한 경우에 어떻게 경우의수가 계산되는지 생각하면

   서 접근해보자.

   우리는, 위에서 N = 1일 때의 DP값들을 모두 구했고 저 식을 초기값으로 사용한다고 하였다.

   그렇다면 첫 번쨰 줄의 경우는 저렇다고 생각하고, 두 번째 줄을 한번 계산해보자.

   1. 두 번째 줄에 사자를 배치하지 않는다고 생각했을 때 경우의 수는??

      - 이 경우에는 첫 번째 줄에 사자가 있든 없든, 왼쪽에 있던 오른쪽에 있던 상관이 없다. 따라서 두번째 줄에 사자를

        배치하지 않는 경우의 수는 총 3가지가 된다.

        3가지인 이유 : 첫 번째 줄에 사자를 배치 안하는 경우, 왼쪽에 배치하는 경우, 오른쪽에 배치하는 경우

   2. 두 번째 줄에 왼쪽에 사자를 배치한다고 생각했을 때의 경우의 수는?

      - 이 경우에는 첫 번째 줄에 사자를 배치하지 않던가, 사자를 오른쪽에 배치했을 경우에만 사자를 배치할 수 있다.

        따라서, 경우의 수는 2가지가 된다.

        2가지인 이유 : 첫 번째 줄에 사자를 배치 안하는 경우, 오른쪽에 배치한 경우

   3. 두 번쨰 줄에 오른쪽에 사자를 배치한다고 생각했을 떄의 경우의 수는?

      - 이 경우는 2번과 반대 경우이다. 따라서 경우의 수는 2번과 마찬가지로 2가지가 된다.

   따라서, N=2일 때의 경우의수는 3 + 2 + 2 = 7 총 7가지가 된다.

   여기서 우리는 점화식을 도출해 낼 수가 있다.

2) 점화식을 말하기 전에 본인이 말했던 DP[][] 배열의 의미를 다시 한번 정리해보자.

   DP[][] 는 경우의 수를 저장하는 배열이었고, DP[a][b]에서 b자리에 있는 놈은 3칸만 할당되었으며, 0일 경우에는

   사자를 배치하지 않을 떄의 경우의 수, 1일 경우에는 사자를 왼쪽에 배치할 때의 경우의 수, 2일 경우에는 사자를 오른쪽에

   배치할 때의 경우의 수를 의미한다고 하였다.

   다시 점화식으로 돌아와보자.

   우리는 N = 2를 예를들어서 풀이를 할 때, 3가지의 경우 모두를 생각해줘야 한다고 했다.

   1. 현재 줄에 사자를 배치하지 않을 때의 경우의 수

   2. 현재 줄에 사자를 왼쪽에 배치할 때의 경우의 수

   3. 현재 줄에 사자를 오른쪽에 배치할 때의 경우의 수

  

   1번 경우에는 이전 줄에 사자를 배치하지 않은 경우, 사자를 왼쪽, 오른쪽에 배치하는 경우 3가지의 경우를 더한 값이

   결과가 되었다.

   2번 경우에는 이전 줄에 사자를 배치하지 않은 경우, 사자를 오른쪽에 배치하는 경우를 더한 값이 결과가 되었고,

   3번 경우에는 이전 줄에 사자를 배치하지 않은 경우, 사자를 왼쪽에 배치하는 경우를 더한 값이 결과가 되었다.

   이를 통해서 점화식을 도출해보면...

   DP[i][0] = DP[i-1][0] + DP[i-1][1] + DP[i-1][2]

   DP[i][1] = DP[i-1][0] + DP[i-1][2]

   DP[i][2] = DP[i-1][0] + DP[i-1][1]

   가 된다. 이 점화식을 통해서 2 ~ N까지의 모든 경우의수를 구해서 N번째 줄일 때의 결과를 도출한다면

   정답을 받아낼 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 100000 + 1
#define Moduler 9901
using namespace std;
 
int N;
int DP[MAX][3];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    DP[1][0] = DP[1][1] = DP[1][2] = 1;
 
    for(int i = 2; i <= N; i++)
    {
        DP[i][0] = (DP[i - 1][0] + DP[i - 1][1] + DP[i - 1][2]) % Moduler;
        DP[i][1] = (DP[i - 1][0] + DP[i - 1][2]) % Moduler;
        DP[i][2] = (DP[i - 1][0] + DP[i - 1][1]) % Moduler;
    }
 
    cout << (DP[N][0] + DP[N][1] + DP[N][2]) % Moduler << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}