백준 1309 동물원

 

 

풀이법

 

package algo;

import java.util.Arrays;
import java.util.Scanner;

public class Solution20 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		// 한줄의 경우에 수는 3가지이다.
		//오른쪽, 왼쪽, 안넣는경구
		//그러므로 0 - 안넣음 1- 왼쪽 2 - 오른쪽  으로 가정하고 
		int arr[][] = new int[n+1][3];
		
		arr[1][0]= 1;
		arr[1][1]= 1;
		arr[1][2]= 1;
		
		
		for(int i = 2 ; i <= n ; i++) {
			arr[i][0] = arr[i-1][0]+arr[i-1][1] + arr[i-1][2];
			arr[i][1] = arr[i-1][0]+arr[i-1][2];
			arr[i][2] = arr[i-1][0]+arr[i-1][1];
		
			arr[i][0] = arr[i][0] %9901; 
			arr[i][1] = arr[i][1] %9901; 
			arr[i][2] = arr[i][2] %9901; 
		}
		
		
		
		int sum = arr[n][0]+arr[n][1]+arr[n][2];
	
		System.out.println(arr[n][0]);
		System.out.println(arr[n][1]);
		System.out.println(arr[n][2]);
		System.out.println("----------------------------");
		
		
		System.out.println(sum%9901);
		
		
		
	}
}

 

 

2*n 칸인 우리에 넣을수 있는 경우의 수를 3가지로 정의하였다.

0 -> 넣지 않을때 

1 -> 왼쪽에 넣을때

2 -> 오른쪽에 넣을때

또한  호랑이가 들어간 우리의 가로 세로에는 호랑이를 넣을 수 없다.

[i][0] 이면 호랑이를 넣지 않는다는 의미 이므로  [i-1][0] [i-1][1] [i-1][2]

[i][1] 이면 왼쪽에 호랑이를 넣겠다 전우리에  오른쪽 or 넣지않음

[i][2] 이면 오른쪽 이기때문에 왼쪽 or 넣지않음이 될 수 있다.