[백준] 1309번 동물원

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

1309번: 동물원

 

dp[n][0] :사자를 넣지 않은 경우 => 모든 경우의 수

dp[n][1] : 사자를 왼쪽 우리에 넣는 경우 :=> 한 줄 위의 오른쪽 우리 사자 => dp[n-1][2]

dp[n][2] : 사자를 오른쪽 우리에 넣는 경우 => 한 줄 위의 왼쪽 우리 사자 => dp[n-1][1]

 

import java.util.*;
import java.io.*;

public class Main {

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

        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;
        int mod = 9901;
        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;
        }

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