[백준 1309] 동물원(JAVA)

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

1309번: 동물원

 

 

 

dp[N][3] 배열은 만들어 dp[i][1]에는 i번째 첫번째 열에 사자를 넣을 수 있는 경우의 수,

dp[i][2]에는 i번째 두번째 열에 사자를 넣을 수 있는 경우의 수,

dp[i][0]에는 i번째 줄에 사자를 하나도 넣지 않은 경우의 수가 들어가도록 해줬다.

 

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

public class Main {

	final static int MOD=9901;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[][] dp=new int[N][3]; //0두칸모두빈칸, 1 왼쪽칸에 배치, 2오른쪽칸에 배치
		dp[0][0]=1;
		dp[0][1]=1;
		dp[0][2]=1;
		for(int i=1; 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-1][0]+dp[N-1][1]+dp[N-1][2])%MOD);

	}

}