BOJ#1309 동물원

BOJ#1309 동물원

* 문제

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

* 풀이

N이 1일 때부터 3일때까지 그림을 직접 그려보면 규칙을 찾으실 수 있을겁니다.

점화식

dp[row][0] = (dp[row - 1][0] + dp[row - 1][1] + dp[row - 1][2]) % MOD;
dp[row][1] = (dp[row - 1][0] + dp[row - 1][2]) % MOD;
dp[row][2] = (dp[row - 1][0] + dp[row - 1][1]) % MOD;

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%231309/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int N;
    static final int MOD = 9901;
    static int[][] dp = new int[100001][3];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        // 0 : 양쪽 모두 비어있는 경우, 1 : 왼쪽에 사자가 있는 경우, 2 : 오른쪽에 사자가 있는 경우
        dp[0][0] = 1;
        dp[0][1] = 1;
        dp[0][2] = 1;

        for (int row = 1; row < N; row++) {

            dp[row][0] = (dp[row - 1][0] + dp[row - 1][1] + dp[row - 1][2]) % MOD;
            dp[row][1] = (dp[row - 1][0] + dp[row - 1][2]) % MOD;
            dp[row][2] = (dp[row - 1][0] + dp[row - 1][1]) % MOD;
        }

        int answer = 0;
        for (int i = 0; i < 3; i++) {
            answer += dp[N - 1][i];
            answer %= MOD;
        }

        System.out.println(answer);
    }
}