동물원 (백준 1309번) [JAVA]

문제 링크 : www.acmicpc.net/problem/1309

1309번: 동물원

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128 MB	10467	5299	4265	49.232%

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

 

풀이

수학적으로 풀어야 하는 문제이다.

처음에 생각한 식이

사자 L마리를 N칸에 넣는다고 할때, 맨 밑에줄에 한마리를 넣고 나머지 L-1마리를 N-1개에 넣는것과

맨 밑에줄에 안넣고 N-1칸에 L마리를 넣는 경우의 수가 있다.

그때 맨 밑에줄에 한마리를 넣고, 나머지 L-1마리를 N-1칸에 넣는 경우를 볼때,

단순히 N-1칸에 L-1마리를 넣는것과는 다르다. 왜냐하면 한마리 넣은거 옆에는 넣으면 안되기 때문.

N-1칸에 L-1마리를 넣는데 한마리 넣은거 옆에를 빼고 생각하면

N-2칸에 L-2마리를 넣는 경우의 수이다.

이것을 계속 나열해보면..

$F(N,L) = 2*[F(N-1,L-1)- F(N-2,L-2)+.-.+.-]+F(N-1,L)$ 이렇게 된다.

하지만 이 식만을 이용하여 2차원 배열로DP를 했다간, 메모리 초과를 맞을 수 있다.

그렇다면 다시한번 식을 풀어보자

$(0,0)$

$(1,0) (1,1)$

$(2,0)(2,1)(2,2)$

$(3,0)(3,1)(3,2)(3,3)$

(2,0)과 (2,2)는 고정이니깐 (1,0),(1,1) 로 바꿀 수 있고, (2,1)을 보면 = 2*(1,0) + (1,1)이다

$N_2$ 를 N=2일때 경우의 수라고 하면 (1,0) + 2*(1,0) + (1,1) + (1,1) = 3(1,0) + 2(1,1). 이때 (1,0) = (0,0)이므로 2(1,0) + 2(1,1) + (0,0)

식을 잘 살펴보면 2*$N_1$ + $N_0$ 임을 알 수 있다.

$N_3$을 본다면, (3,0) = (2,0), (3,3) = (2,2), (3,1) = 2*(2,0) + (2,1), (3,2) = 2 *{(2,1)-(1,0)} + (2,2)이다.

식을 정리해주면

$N_3$ = 3(2,0) + 3(2,1)+ 2(2,2) - 2(1,0) 이때 (2,0) = (1,0)이고 (2,1) = 2(1,0) + (1,1)이므로 다시 정리하면

$N_3$ = 2(2,0) + 2(2,1) + 2(2,2) + (1,0) + 2(1,0) + (1,1) - 2(1,0) = $2*N_2 + N_1$ 로 정리된다.

결국 $N>1에서 N_n = 2N_{n-1}+N_{n-2}$ 로 정리할 수 있다.

 

코드

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    public static int[][] lions;
    public static void main(String[] args)throws Exception {
        int N = Integer.parseInt(br.readLine().trim())+1;
    	int ans = 0;
    	lions = new int[N][N];
    	
    	for(int i=0; i<N; i++) {
    		for(int j=0; j<N; j++) {
    			lions[i][j] = 0;
    		}
    	}
    	
    	for(int i=0; i<N; i++) {
    		for(int j=0; j<=i; j++) {
    			path(i,j);
    		}
    	}
    	
    	for(int i=0; i<N; i++) {
    		ans = (ans + lions[N-1][i])%9901;
    	}
    	
    	//printBoard(N, lions);
    	System.out.println(ans);
    	
    }
    
    public static int path(int n, int l) {
    	if(n < l) {
    		return 0;
    	}
    	if(lions[n][l] != 0) {
    		return lions[n][l];
    	}
    	if(l==0) {
    		lions[n][l] = 1; return lions[n][l];
    	}
    	if(n==l) {
    		lions[n][l] = 2; return lions[n][l];
    	}
    	if(l==1) {
    		lions[n][l] = 2*n; return lions[n][l];
    	}


    	int check = 0;
    	
    	for(int i =1; i<=l; i++) {
    		check = check + lions[n-i][l-i];
    		check = check * (-1);
    	}
    	
    	check = Math.abs(check);
    	int temp = 2*(check) + lions[n-1][l];
    	lions[n][l] = temp;
    	
    	return temp;
    }
}

 

결과