[BOJ_1309/JAVA] 동물원

문제

풀이

두칸을 기준으로

1. 사자가 한마리도 없을 때

2. 사자가 왼쪽에 있을 때

3. 사자가 오른쪽에 있을 때

로 나누어야한다.

 

그 전 두칸에서의 경우의 수 + 두칸이 추가되었을 때 경우의 수를 구하면 된다.

dp[1][0]=1;

dp[1][1]=1;

dp[1][2]=1; 

N이 1일때는 1로 동일하므로 초기화를 시켜준다.

 

그리고 두칸이 추가되었을 때는

1) 사자가 한마리도 없을 때, dp[2][0]=dp[1][0]+dp[1][1]+dp[1][2]

2) 사자가 왼쪽에 있을 때, dp[2][1]=dp[1][0]+dp[1][2]

(위아래로 배치되면 안되기때문에 전 칸에서 아무것도 배치되지 않을 때+사자가 오른쪽에 있을 때)

3) 사자가 오른쪽에 있을 때, dp[2][2] = dp[1][0]+dp[1][1]

(전 칸에서 아무것도 배치되지 않을 때 + 사자가 오른쪽에 있을 때)

 

따라서 점화식은

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

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

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

가 된다.

이것을 코드로 구현해보자.

코드

package Week08;

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

public class BOJ1309 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		final int mod = 9901;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int dp[][] = new int[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][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);
	}

}