[백준] 동물원 1309 - JAVA

문제

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

1309번: 동물원

풀이

이차원 배열을 이용하여 세가지 경우의 수를 나타낸다.

dp[n][0] -> 두 개의 방 중에 사자를 아예 넣지 않은 경우
dp[n][1] -> 두 개의 방 중에 사자를 왼쪽 방에 넣은 경우
dp[n][2] -> 두 개의 방 중에 사자를 오른쪽 방에 넣은 경우

 

코드는 다음과 같다

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]) => 오른쪽에 넣기 때문에 이전방은 왼쪽이거나 없어야 한다

코드

import java.util.*;
import java.io.*;

public class Main {
	static int count = 0;
	
	public static void main(String args[]) throws IOException {
		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]) % 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.print((dp[n][0] + dp[n][1] + dp[n][2]) % 9901);
	}
}