백준 1309) 동물원 java

분석

---

처음에는 사자가 1 ...n 마리 인 경우로 나눠서 생각해서 시간을 꽤 허비했다.

하지만 이렇게 접근하면 코드가 너무 복잡해지므로 , 사자가 아닌 '우리'를 기준으로 생각을 해야한다.

 

우리가 2X2 인 경우(N=2) , 두 번째 줄에 사자를 넣는 경우는 총 세가지이다.

1. 첫번째 칸에 사자를 넣는 경우

사자

2. 두번째 칸에 사자를 넣는 경우

	사자

3. 사자를 안넣는 경우

 

각 경우에 대해서 경우의 수를 구해주어야한다.

 

1번의 경우는 첫번째 줄에 두번째칸에 사자를 넣거나 , 아예 안 넣는 경우가 있다. (2개의 경우의 수)

2번의 경우는 첫번째 줄에 첫번째칸에 사자를 넣거나 , 아예 안 넣는 경우가 있다. (2개의 경우의 수)

3번의 경우는 첫번째 줄에 첫번째,두번째칸에 사자를 넣거나 , 아예 안 넣는 경우가 있다. (3개의 경우의 수)

 

이를 식으로 표현하면 다음과 같이 표현할 수 있다.

dp[2][1] = dp[1][0] + dp[2]; // 1번 경우

dp[2][2] = dp[1][0] + dp[0]; // 2번 경우

dp[2][0] = dp[1][0] + dp[1][1] + dp[2]; // 3번 경우

 

이제 우리의 크기를 늘려가면서 경우의 수를 구해주면 된다.

 

우리가 2X3 인 경우(N=3) , 

위와 같은 방법으로 구해주면 된다.

 

우리가 2X4 인 경우(N=4) , 

위와 같은 방법으로 구해주면 된다.

 

코드

---

import java.util.Scanner;


public class Main {

    static long[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        dp = new long[num + 1][3];

        dp[1][0] = dp[1][1] = dp[1][2] = 1;

        for (int i = 2; i <= num; i++) {
            dp(i);
        }

        long result = (dp[num][0] + dp[num][1] + dp[num][2]) % 9901;

        System.out.println(result);
    }

    static void dp(int num) {
        dp[num][0] = (dp[num - 1][1] + dp[num - 1][2] + dp[num - 1][0]) % 9901;
        dp[num][1] = (dp[num - 1][0] + dp[num - 1][2]) % 9901;
        dp[num][2] = (dp[num - 1][0] + dp[num - 1][1]) % 9901;
    }

}