1309. 동물원

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

1309번: 동물원

 

풀이

필요 알고리즘: 다이나믹 프로그래밍(DP)

 

사자가 서로 인접하지 않도록 배치하는 경우의 수를 찾아야 하는데, N의 최대 크기가 심히 크다. 최대 20만 칸의 우리에서, 0~10만 마리의 사자를 배치하는 경우의 수를 찾아야 하는데, 이만한 수치를 백트래킹 등으로 2초 안에 푸는 것은 불가능하다. 그래서 DP를 통해 변칙적인 방법으로 풀고자 한다.

 

그림 1. 2 × 1 배열에서 사자를 인접하지 않게 배치하는 경우

우선 2 × 1 크기의 배열에서 사자를 인접하지 않게 배치하는 경우의 수를 생각해 보자. 사자를 아예 배치하지 않는 것도 경우의 수라고 했으므로, 위 그림처럼 3가지 경우가 있을 것이다. 이제 이 세 경우를 바탕으로 하여 DP를 적용할 것이다.

 

그림 2.  2 × i 배열에서 사자를 인접하지 않게 배치하는 경우

N × 3 크기를 가진 2차원 배열 dp를 선언하자. dp[i][0]은 i번째 행에 사자를 놓지 않을 때, dp[i][1]은 i번째 행의 첫 번째 칸에, dp[i][2]는 두 번째 칸에 사자를 각각 배치할 때 경우의 수이다.

 

그러면 이제 점화식을 생각해 보자. 먼저 i = 1일 때 초기값은 그림 1에 의해 dp[1][0], dp[1][1], dp[1][2] 모두 1이다.

 

그림 3. dp[2][0]

i = 2일 때, 2행에 사자를 놓지 않으면 1행은 세 가지 경우가 가능하다. 즉, dp[2][0] = dp[1][0] + dp[1][1] + dp[1][2]이다.

 

그림 4. dp[2][1]

2행의 첫 번째 칸에 사자를 놓을 경우, 1행의 첫 칸에는 사자를 놓을 수 없다. 따라서 두 가지 경우가 가능하며, 식으로 표현하면 dp[2][1] = dp[1][0] + dp[1][2]이다.

 

그림 5. dp[2][2]

2행의 두 번째 칸에 사자를 놓을 경우, 1행의 두 번째 칸에는 사자를 놓을 수 없다. 따라서 두 가지 경우가 가능하며, 식으로 표현하면 dp[2][2] = dp[1][0] + dp[1][1]이다.

 

위를 일반화하여 점화식으로 나타내면 다음과 같다.

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]

 

시간 복잡도

행의 개수가 \(N\)인 우리에서 경우의 수를 구하기 위해 \(3N\)번의 연산을 수행하므로 시간 복잡도는 \(O(3N)\)이다.

 

소스코드

#include <iostream>
#define DIV    9901
using namespace std;

int N;
int dp[100001][3];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N;
    dp[1][0] = 1; dp[1][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]) % DIV;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % DIV;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % DIV;
    }
    
    cout << (dp[N][0] + dp[N][1] + dp[N][2]) % DIV;
    return 0;
}