[JAVA] 백준 1309번 : 동물원

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

1309번: 동물원

---

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    final static int mod = 9901;
    static int[][] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        dp = new int[N + 1][3];
        Arrays.fill(dp[1], 1);
        for (int k = 2; k <= N; k++) {
            dp[k][0] = (dp[k - 1][0] + dp[k - 1][1] + dp[k - 1][2]) % mod;
            dp[k][1] = (dp[k - 1][0] + dp[k - 1][2]) % mod;
            dp[k][2] = (dp[k - 1][0] + dp[k - 1][1]) % mod;
        }
        System.out.println(Arrays.stream(dp[N]).sum() % mod);
    }
}

💡 DP

풀이

• 사자가 0 ~ N마리 존재 가능
• N마리를 넣는 경우의 수는 무조건 2가지 (왼쪽 시작/ 오른쪽 시작)
• 2*K 배열에서 2*(K+1) 배열로 넘어갈 때, 맨 위에 한 줄(2칸)이 추가된다고 생각하자.
  • 한 줄이 추가 된다는 건 넣을 수 있는 사자 수가 1마리 늘어난 다는것 => 늘어난 사자를 추가하냐/안하냐로 나뉨
  • 만약 사자를 왼쪽에 추가한다면, 그 밑에 줄은 왼쪽 배치 시작일 수 없음
  • 즉, 사자 배치 경우의 수를 크게 3가지로 분리하고, 한 줄 추가됐을 때 이것을 바탕으로 계산해 나가면 됨

✅ 즉, 한 마리 늘어난 사자를 추가된 줄 왼쪽에 넣냐 / 오른쪽에 넣냐 / 넣지 않냐 => 이렇게 3가지 경우로 나누자 
      dp[N][0] : 우리가 2*N 칸일 때, 첫 줄 왼쪽/오른쪽에 모두 배치 안하는 경우
      dp[N][1] : 첫 줄 왼쪽에 사자를 배치하는 모든 경우의 수
      dp[N][2] : 첫 줄 오른쪽에 사자를 배치하는 모든 경우의 수

• dp[3][0] = dp[2][0] + dp[2][1] + dp[2][2] 
  • 추가 줄에 아무것도 넣지 않는 경우는 모든 경우에서 가능하다
• dp[3][1] = dp[2][0] + dp[2][2]
  • 추가된 줄에 왼쪽에 사자를 넣는다면, 아래 줄엔 양쪽 다 비워져 있거나 / 오른쪽에 있어야 한다
• dp[3][2] = dp[2][0] + dp[2][1]

🔸  점화식
    - dp[k][0] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2]
    - dp[k][1] = dp[k-1][0] + dp[k-1][2]
    - dp[k][2] = dp[k-1][0] + dp[k-1][1]