백준 1309 자바 - 동물원

문제

---

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

1309번: 동물원

 

 

 

문제해결

---

- dp[n][0] : 사자를 넣지 않는 경우, 모든 경우의 수를 더해야됨

- dp[n][1] : 사자를 왼쪽 우리에 넣는 경우, 바로 위쪽에 있는 경우를 제외한 모든 경우를 더함

- dp[n][2] : 사자를 오른쪽 우리에 경우, 바로 위쪽에 있는 경우를 제외한 모든 경우를 더함

import java.util.Scanner;

public class B1309 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] dp = new int[n+1][3];
        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]) % 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;
        }

        System.out.println((dp[n][0] + dp[n][1] + dp[n][2]) % 9901);
    }
}