1309 동물원

문제

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

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

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

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

예제 입력 1

4

예제 출력 1

41

코드

import java.io.*;

public class P_1309 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[][] dp = new int[n + 1][3];

        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]) % 9901;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
        }

        bw.write(Integer.toString((dp[n][0] + dp[n][1] + dp[n][2]) % 9901));
        bw.flush();
    }
}

코드 설명

이 문제는 dp문제이다.
브루트포스로 풀지 못하는 이유는 한 칸당 선택할 수 있는 경우의 수가 (1번째 칸에만 사자 배치), (2번째 칸에만 사자 배치), (사자 배치하지 않음) 이렇게 세 가지인데 세로의 최댓값으로 100000이 들어왔을 때 3^100000이 되므로 문제의 시간 제한 조건인 2초를 훌쩍 넘겨버린다.

먼저, dp[N]을 2xN칸에 사자를 배치하는 경우의 수라고 생각했다.
이렇게 생각했을 때 N번째 칸에 사자를 배치하는 방법은 이전 칸인 N-1에 사자를 어떻게 배치했는지에 영향을 받는다.

그래서 이차원배열인 dp[i][j]로 배열을 수정했다.
i는 i번째 칸을 뜻하고,
j는 0, 1, 2가 존재하면 0은 사자를 배치하지 않는 방법의 수, 1은 1번째 칸에만 사자를 배치하는 경우의 수, 2는 2번째 칸에만 사자를 배치하는 경우의 수로 쓰인다.
i칸에 사자를 두 마리 배치하는 경우는 문제에서 제한되었으므로 고려하지 않았다.

이제 생각을 해 보면 i번째에 사자를 아예 놓지 않는 경우는 i-1번째 칸에 사자가 어디에 놓여있든 상관이 없다.
그러므로 dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]가 dp[i][0]의 점화식이 된다.

1번째 칸에만 사자를 놓는 경우 i-1번째 칸에서도 1번째 칸에 사자를 놓은 경우만 피하면 된다.
i-1번째의 2번째 칸에 사자가 놓여있거나 사자가 어느 칸에도 놓여있지 않을 때 안전하다.
그러므로 dp[i - 1][0] + dp[i - 1][2]가 dp[i][1]의 점화식이 된다.

2번째 칸에만 사자를 놓는 경우 i-1번째 칸에서도 2번째 칸에 사자를 놓은 경우만 피하면 된다.
i-1번째의 1번째 칸에 사자가 놓여있거나 사자가 어느 칸에도 놓여있지 않을 때 안전하다.
그러므로 dp[i - 1][0] + dp[i - 1][1]이 dp[i][2]의 점화식이 된다.

$dp[N][0] = dp[N-1][0] + dp[N-1][1] + dp[N-1][2]$

그리고 최종적으로 N번째 줄에 사자를 배치하는 모든 경우의 수는 dp[N][0], dp[N][1], dp[N][2]를 모두 더하면 된다.

하나 더 봐야할 것은 dp[1]의 요소를 모두 1로 초기화했다는 것이다.
주어진 표의 첫번째 줄만 살펴보면 이전 줄이 없기 때문에 앞서 말했던 세 가지 경우가 모두 존재한다.
(1번째 칸에만 사자 배치), (2번째 칸에만 사자 배치), (사자 배치하지 않음)
그러므로 각각의 배열 요소 dp[1][1], dp[1][2], dp[1][0]을 모두 1로 초기화를 하고 시작을 한다.