[백준 1309] 동물원 (JAVA)

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

1309번: 동물원

 

dp[n+1][3]

dp[n][0] -> n행의 0열은 n행에 아무것도 넣지 않았을때를 뜻함

dp[n][1] -> n행의 1열은 1번째 열에 사자를 넣을 경우의 수를 뜻함

dp[n][2] -> n행의 2열은 2번째 열에 사자를 넣을 경우의 수를 뜻함

 

따라서 점화식은 

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

: 아무것도 넣지 않았을 경우에는 다른 열의 영향이 없기 떄문에 이전 행의 모든 경우의 수를 합한 값이 된다.

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

: 1번째 열에 넣을 경우에는 같은 열인 곳만 사자를 넣지 못하기 떄문에 0열과 2열을 더한 값이다.

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

: 2번째 열에 넣을 경우에는 같은 열인 곳만 사자를 넣지 못하기 떄문에 0열과 1열을 더한 값이다.

 

따라서, dp[n][0]+dp[n][1]+dp[n][2]

1. n행에 모두 넣지 않았을 때

2. 1번째 열에 넣었을 때

3. 2번째 열에 넣었을 때

를 모두 더한 값이 답이 된다.

  

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

public class Main {
	static int[][] dp;
	static int result = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		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]) % 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;
		}

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

}