1309 : 동물원

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

---

문제

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

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

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

입력

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

출력

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

---

접근

• i번째 행에는 사자가 없거나(1), 있다면 왼쪽에 있거나(2), 오른쪽에 있거나(3) 이 세가지로 구분할 수 있다. 

예를 들어, 1번째 행에 사자가 없다면, 2번째 행에는 사자가 없을 수도, 왼쪽에 있을 수도, 오른쪽에 있을 수도 있다.  1번째 행에 사자가 왼쪽에 있다면, 2번째 행에는 사자가 없을 수도, 오른쪽에 있을 수도 있다.  1번째 행에 사자가 오른쪽에 있다면, 2번째 행에는 사자가 없을 수도, 왼쪽에 있을 수도 있다.

• 행의 수가 (n+1), 열의 수가 3인 dp 배열을 만든다. 
• 0번째 열에는, 이전 행에 사자가 없는 경우를, 1번째 열에는, 이전 행에 사자가 왼쪽 칸에 있는 경우를, 2번째 열에는 이전 행에 사자가 오른쪽에 있는 경우를 담는다. 
• 따라서, 점화식은 다음과 같다. 

 

(1)	(2)	(3)
dp[i][0]	dp[i][1]	dp[i][2]
(i-1)번째 행에 사자가 없는 경우의 수 + (i-1)번째 행에 사자가 왼쪽에 있는 경우의 수 + (i-1)번째 행에 사자가 오른쪽에 있는 경우의 수	(i-1)번째 행에 사자가 없는 경우의 수 + (i-1)번째 행에 사자가 오른쪽에 있는 경우의 수	(i-1)번째 행에 사자가 없는 경우의 수 + (i-1)번째 행에 사자가 왼쪽에 있는 경우의 수

---

코드

import java.util.*;
import java.io.*;
 
public class Main {
 
    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 + 2][3];
 
        dp[1][0] = dp[1][1] = dp[1][2] = 1;
 
        for (int i = 2; i <= n + 1; 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(dp[n + 1][0] + "\n");
 
        bw.flush();
        br.close();
 
    }
}