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

 

 🔗 문제 링크 : https://www.acmicpc.net/problem/1309 

 

---

 

문제

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

문제

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

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

 

 

 

 

 

입출력 예시

입출력 예시

 

입출력 예시

 

 

 

---

 

풀이 | Dynamic Programming

우리의 크기가 N 일 때 사자를 배치하는 경우의 수를 DP(N)으로 표현하였습니다.

 

N이 1일 때, 2일 때의 경우의 수는 아래와 같다.

풀이

풀이

 

N = 2 인 경우는, N = 1인 경우에서, 맨 마지막에 한 줄이 확장된 모습이다.

 

N = 3 인 경우는, N = 1인 경우에서, 맨 마지막에 두 줄이 확장된 모습이다.

 

 

 

문제를 풀기 위해서,

N이 증가할 때 어떤 규칙이 있는지 알아야한다.

 

 

첫째,

N = 2 의 맨 위 두 칸이 공백일 때의 경우의 수는 N = 1의 경우의 수와 동일하다.

N = 3 의 맨 위 두 칸이 공백일 때의 경우의 수는 N = 2의 경우의 수와 동일하다.

 

즉, DP(N-1) 으로 표현할 수 있다. 

N = 1과 N = 2의 첫 줄을 제외한 나머지 줄, 즉, 두 번째 줄이 일치하는 모습이다.

N = 3의 노란 박스 구하는 식은 DP(2)이므로, 7이다.

 

둘째,

첫 줄의 왼쪽에 사자가 있을 때의 경우와 오른쪽에 사자가 있을 때의 경우는 

N = 3 일 때는 N = 2 의 경우의 수에 2를 곱한 값이 된다. (첫 번째 줄과 두 번째 줄에 사자가 인접한 경우를 전혀 고려하지 않은 상태)

 

즉, DP(N-1) * 2 로 표현할 수 있다.

위의 경우의 수(주황박스 포함)를 구하는 식은 DP(N-1) * 2이므로 7 * 2 = 14 이다.

 

셋째,

위에서 보았듯이, 사자가 인접하는 경우의 수를 제외해야 한다.

저 문제의 부분(주황색 점선박스)을 보면,

N = 2인 경우의 첫 줄의 왼쪽에 사자가 있을 때의 경우와 오른쪽에 사자가 있을 때의 경우와 동일했다. 

N = 2의 주황박스 부분은 N = 3의 문제의 부분과 일치하다.노

 

N = 2의 노란 박스는 첫 번째 규칙에서 이미 N = 1과 같다는 것을 알았으니, 두 번째 규칙에서 구한 식에서 빼주어야 하는 부분만을 식으로 표현하면 DP(N-1) - DP(N-2) 이다.

 

 

이제 모든 식을 합치면,

• DP(N-1)
• DP(N-1) * 2
• DP(N-1) - DP(N-2)  

DP(N-1) + DP(N-1) * 2 - ( DP(N-1) - DP(N-2) )

=> DP(N - 1) * 2 + DP(N - 2) 가 나온다. (이 점화식을 이용해 문제를 풀어낼 수 있다.)

 

#include <iostream>
using namespace std;

int DP(int size) {
    int n = size;
    int dp[n] = {0};

    dp[1] = 3;
    dp[2] = 7;

    for (int i = 3; i <= n; ++i) {
        dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 9901;
    }

    return dp[n];
}

int main() {
    /* 입력받기 : 우리 크기 N */
    int N;
    cin >> N;

    cout << DP(N);

    return 0;
}

 

 

 

---