백준-1309번/동물원 (java)

 

우선 행의 크기가 N, 열의 크기가 3인 배열을 만들어주자.

long [][] dp=new long[n+1][3];

 

열의 크기가 3인 이유는 N번째 우리에 사자가 들어가는 경우는 [N][0], 첫번째 우리에 들어가 있을 경우 [N][1], 두번째 우리에 들어가 있는 경우 [N][2] 로 해주기 위함이다.

 

점화식 만들기

 

i번째 행의 우리에 사자가 없는 경우 ==> i-1번째 우리에 사자가 없거나, 1번째 우리에 있거나, 2번째 우리에 있는 경우

dp[i][0]=(dp[i-1][1]+dp[i-1][2]+dp[i-1][0])%9901;

 

i번째 행의 1번째 우리에 사자가 있는 경우 ==> i-1번째 우리에 사자가 없거나, 2번째 우리에 있는 경우

dp[i][1]=(dp[i-1][0]+dp[i-1][2])%9901;

 

i번째 행의 2번째 우리에 사자가 있는 경우 ==> i-1번째 우리에 사자가 없거나, 1번째 우리에 있는 경우

dp[i][2]=(dp[i-1][0]+dp[i-1][1])%9901;

 

이와 같은 규칙으로 점화식을 만들 수 있다.

 

점화식을 바탕으로 만든 정답 코드

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

public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n=scanner.nextInt();
		long [][] dp=new long[n+1][3];
		dp[1][0]=1;
		dp[1][1]=1;
		dp[1][2]=1;
		
		for(int i=2; i<=n; i++) {
			dp[i][0]=(dp[i-1][1]+dp[i-1][2]+dp[i-1][0])%9901;
			dp[i][1]=(dp[i-1][0]+dp[i-1][2])%9901;
			dp[i][2]=(dp[i-1][0]+dp[i-1][1])%9901;
		}
		
		long sum=0;
		for(int i=0; i<3; i++) {
			sum=(sum+dp[n][i])%9901;
		}
		System.out.println(sum);
	}
}