백준 1309번 동물원[JAVA]

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

 

문제 이해

 

2*N의 우리에 사자를 배치 해야하는데 조건이 있다.

• 가로, 세로에 인접한 사자가 존재하면 안됨
• 각 우리에는 사자를 배치 할수도 있고, 안할수도 있다.

 

문제 해결

 

각 칸에 사자를 배치 하거나 안하는 경우의 수를 구하기 위해 N*2의 경우에 맞는 2차원 배열을 만들어 줬다.

 

int[][] arr = new int[100001][3];
arr[1][0]=1; //배치X
arr[1][1]=1; //좌측
arr[1][2]=1; //우측

 

 

사자를 배치할때 바로 윗 라인의 경우를 생각해보면

 

사자가 좌측에 존재하는 경우 : 우측 OR 배치 X

사자

 

이것을 수식으로 하면 아래 코드와 같다.

arr[i][1] = (arr[i-1][0]+arr[i-1][2])%MOD;

 

 

사자가 우측에 존재하는 경우 : 좌측 OR 배치 X

	사자

 

이것도 마찬가지로 다음과 같이 표현 가능하다.

arr[i][2] = (arr[i-1][0]+arr[i-1][1])%MOD;

 

 

윗 라인에 사자가 없는 경우

 

이 경우에는 윗라인에 사자가 좌우측 모두 존재 가능하며 없을수도 있으므로 모든 경우의 수를 더해주면 된다.

arr[i][0] = (arr[i-1][0]+arr[i-1][1]+arr[i-1][2])%MOD;

 

 

 

 

전체 코드

import java.util.Scanner;

public class Main {
    static final int MOD = 9901;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[][] arr = new int[100001][3];
        arr[1][0]=1; //배치X
        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])%MOD;
            arr[i][1] = (arr[i-1][0]+arr[i-1][2])%MOD;
            arr[i][2] = (arr[i-1][0]+arr[i-1][1])%MOD;
        }
        System.out.println((arr[n][0]+arr[n][1]+arr[n][2])%MOD);
    }
}