[JAVA]백준1309번 동물원

문제는 다음과 같다.

오늘은 백준1309번 동물원 문제를 풀어보도록 하자. 하나하나씩 해보다가 규칙성을 찾았다. 하지만 너무 야매(?) 같다고 해야하나.. 얼떨결에 끼워맞춘 기분이라 정확한 로직을 이해하기 위해 다른 블로그를 찾아보았다.

우선 내가 찾은 규칙성은 dp[N] = dp[N-1]x2 + dp[N-2] 이다. 정확한 로직을 이해하기 위해 마이구미님의 블로그를 이용했다.

규칙성은 다음과 같다.

1. 만일 현재의 우리에 어떠한 사자도 없다? -> 위의 우리에는 어떠한 사자도 없을 수도 있다 or 왼쪽에 있을 수 있다 or 오른쪽에 있을 수 있다. => dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]

2. 만일 현재의 우리 왼쪽에 사자가 있다? -> 위의 우리에는 어떠한 사자도 없을 수도 있다 or 오른쪽에 있을 수 있다. => dp[i][1] = dp[i-1][0] + dp[i-1][2]

3. 만일 현재의 우리 오른쪽에 사자가 있다? -> 위의 우리에는 어떠한 사자도 없을 수도 있다 or 왼쪽에 있을 수 있다. => dp[i][2] = dp[i-1][0] + dp[i-1][1]

위와 같이 3가지의 경우로 나눌 수 있고, answer = (dp[N][0] + dp[N][1] + dp[N][2]) % 9901로 나타낼 수 있다.

                                     [코드]
                                     
                                     -첫 번째 방법-
                                     
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_1309 {
    public static int N;
    public static long dp[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        dp = new long [N+1];
        dp[0] = 1;dp[1] = 3;
        long temp;
        for(int i=2;i<=N;i++) {
            temp = (dp[i - 1] * 2) % 9901 + (dp[i - 2]) % 9901;
            dp[i] = temp % 9901;
        }
        System.out.println(dp[N]);
    }
}

                                     -두 번째 방법-
                                     
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_1309 {
    public static int N;
    public static long dp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        dp = new long [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;
        }
        long answer = (dp[N][0] + dp[N][1] + dp[N][2])%9901;
        System.out.println(answer);
    }
}