[Java] 백준 1309 : 동물원

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

1309번: 동물원

---

 

dp [N+1][3]에서

dp [n][0] 은 사자가 n행에 한 마리도 없을 때, 

dp [n][1] 은 사자가 1행에서 왼쪽에 한 마리 있을 때,

dp [n][2] 은 사자가 1행에서 오른쪽에 한 마리 있을 때를 의미한다. 

i=0일 때,

dp [i][0] 일 때는 i-1행에서 사자가 어느 곳에 있어도 되므로, 앞행에 사자가 없거나 왼쪽에 있거나 오른쪽에 있는 경우를 더한다. => dp [i][0]=dp [i-1][0]+dp [i-1][1]+dp [i-1][2];

dp [i][1] 일 때는 i-1행에서 사자가 없거나 오른쪽에만 있어야 하므로 그 경우를 더한다. => dp[i][1]=dp[i-1][2]+dp[i-1][0];

dp [i][2] 일 때는 i-1행에서 사자가 없거나 왼쪽에만 있어야 하므로 그 경우를 더한다. => dp[i][2]=dp[i-1][1]+dp[i-1][0];

---

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

public class Main {

	static int N;
	static int[][] dp;
	static final int num=9901;
	public static void main(String[] args) throws IOException  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); // N
		dp = new int[N+1][3];
		
		Arrays.fill(dp[1], 1);
		
		
		for(int i=2;i<=N;i++) {
			dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%num;
            dp[i][1]=(dp[i-1][2]+dp[i-1][0])%num;
            dp[i][2]=(dp[i-1][1]+dp[i-1][0])%num;
		}
		
		System.out.println(Arrays.stream(dp[N]).sum()%num);
				
	}// main()

}// class Main