알고리즘 :: 백준 :: DP :: 1309 :: 동물원

문제

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

문제접근

1. https://velog.io/@embeddedjune/알고리즘-백준-DP-11727-2xn-타일링2 2xn 타일링 문제와 거의 똑같은 문제다. 다만 차이가 있다면 이번에는 $n\times 2$ 타일을 $1\times 2$ 타일과 $2\times 1$ 타일로 채우는 문제라는 것이다.

2. 사자를 놓는 경우의 수를 생각해보자.

   0	1
   X	X
   ○	X
   X	○

   N번째 행에 대해 사자를 놓는 경우의 수는 위와 같이 3가지다.

   • 사자를 아예 놓지 않는 경우
   • 사자를 왼쪽에 놓는 경우
   • 사자를 오른쪽에 놓는 경우

3. $D[n][0], [n][1], [n][2]$가 각 경우의 수를 의미한다고 가정하자.
   1. $D[n][0] = D[n-1][0]+D[n-1][1]+D[n-1][2]$ 이다.
   왜냐하면 n행에 사자를 놓지 않으면 n-1행에는 사자를 자유롭게 놓을 수 있기 때문이다.
   2. $D[n][1] = D[n-1][0]+D[n-1][2]$
   n행의 왼쪽에 사자를 놓으면 n-1행에는 왼쪽에 사자를 놓을 수 없다.
   3. $D[n][2] = D[n-1][0]+D[n-1][1]$
   n행의 오른쪽에 사자를 놓으면 n-1행에는 오른쪽에 사자를 놓을 수 없다.
   

코드

#include <iostream>
using namespace std;
using ll = long long;

int n;
ll dp[100001][3] = {{0, 0, 0}, {1, 1, 1}, };

ll solve(int height, int whatCase) {
    if (height < 0) return 0;
    if (dp[height][whatCase] > 0) return dp[height][whatCase];
    /*  dp[n][0]: 사자를 놓지 않는 경우, [1]: 왼쪽에 놓는 경우, [2]: 오른쪽에 놓는 경우
        dp[n][0]: [n-1][0], [1], [2] 모두 가능함.
        dp[n][1]: [n-1][1]은 불가능함, dp[n][2]: [n-1][2]는 불가능함.
    */
    if (whatCase == 0)
        return dp[height][0] = (solve(height - 1, 0) + solve(height - 1, 1) + solve(height - 1, 2)) % 9901;
    else if (whatCase == 1)
        return dp[height][1] = (solve(height - 1, 0) + solve(height - 1, 2)) % 9901;
    else 
        return dp[height][2] = (solve(height - 1, 0) + solve(height - 1, 1)) % 9901;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    
    ll ans = 0;
    for (int i = 0; i < 3; ++i)
        ans = (ans + solve(n, i)) % 9901;
    cout << ans << '\n';
}	

결과