DP / 백준 1309 동물원

 

문제 접근

dp[i][0] ~ dp[i][2] 차례대로 두칸모두비었음, 왼쪽, 오른쪽으로 나눔

두칸 모두 비었을 때는 전 줄의 어떤 경우가 와도 됨

왼쪽일 때는 전 줄의 비었을 때와 오른쪽인 경우만

오른쪽일 때는 전 줄의 비었을 떄와 왼쪽인 경우만

풀이

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

public class S1309 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int mod = 9901;
        int[][] dp = new int[N + 1][3];

        Arrays.fill(dp[1], 1);

        for (int i = 2; i <= N; i++) {
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
        }

        int result = (dp[N][0] + dp[N][1] + dp[N][2]) % mod;

        System.out.println(result);
    }
}