[백준 1309, Java] 동물원

문제

www.acmicpc.net/problem/1309

1309번: 동물원

 

check

zoo[i][j] = i번째 우리에 동물을 넣을 때 동물을 넣지 않는 경우의 수(j=0), 1번열에 넣는 경우(j=1), 2번열에 넣는 경우(j=2) 라고 정의하면, 점화식은

zoo[i][0] = zoo[i-1][0] + zoo[i-1][1] +zoo[i-1][2],

zoo[i][1] = zoo[i-1][0] +zoo[i-1][2]

zoo[i][2] = zoo[i-1][0] +zoo[i-1][1] 이 된다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Member;

public class Main {
    public static int N;
    public static int[][] zoo;
    public static int MOD = 9901;

    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        /*
            zoo[i][j] = i번째 우리에 동물을 안넣는 경우의수(j=0), 1열에 넣는 경우의 수(j=1), 2열에 넣는 경우의 수(j=2)
            zoo[i][0] = zoo[i-1][0] +zoo[i-1][1] + zoo[i][1]
            zoo[i][1] = zoo[i-1][0] + zoo[i][2]
            zoo[i][2] = zoo[i-1][0] + zoo[i][1]
         */

        zoo = new int[N][3];
        int result = getNumberOfCasesOfZoo();

        bw.write(String.valueOf(result));
        bw.flush();

        br.close();
        bw.close();

    }
    public static int getNumberOfCasesOfZoo(){
        for(int row = 0; row<N ; row++){
            if(row==0){
                zoo[row][0] = 1;
                zoo[row][1] = 1;
                zoo[row][2] = 1;
            }
            else{
                zoo[row][0] = (zoo[row-1][0]+zoo[row-1][1]+zoo[row-1][2]) % MOD;
                zoo[row][1] = (zoo[row-1][0] + zoo[row-1][2]) % MOD;
                zoo[row][2] = (zoo[row-1][0] + zoo[row-1][1]) % MOD;
            }
        }

        return (zoo[N-1][0] + zoo[N-1][1] + zoo[N-1][2]) % MOD;
    }
}