[백준] 1309 동물원 - 동적계획법(Dynamic Programming, DP) JAVA

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

1309번: 동물원

코드설명

DP 문제입니다.

 

처음 문제를 봤을때 첫번쨰 칸과 두번째 칸에 각각 나눠서 사자를 배치하는 경우는 생각할 수 있었으나,

아예 두 칸에 배치하지 않는경우를 DP[N][0] 으로 표현한다는 생각을 못했었습니다.

DP를 아래와 같이 정의했습니다.

dp = new long[N+1][3]; // N번쨰 행에서 [N][0] : 사자를 배치하지 않는경우, [N][1]:첫번째 칸에 사자를 배치하는경우, [N][2]:두번째 칸에 사자를 배치하는경우
dp[1][0] = 1; //사자를 배치하지 않는경우
dp[1][1] = 1; //첫번쨰 줄의 첫번쨰 칸에 사자를 배치하지 않는경우
dp[1][2] = 1; //첫번째 줄의 두번쨰 칸에 사자를 배치하지 않는경우

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N;
	public static long[][] dp;
	public static int answer;
	public static int MOD = 9901;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new long[N+1][3]; // N번쨰 행에서 [N][0] : 사자를 배치하지 않는경우, [N][1]:첫번째 칸에 사자를 배치하는경우, [N][2]:두번째 칸에 사자를 배치하는경우
    	dp[1][0] = 1; //사자를 배치하지 않는경우
    	dp[1][1] = 1; //첫번쨰 줄의 첫번쨰 칸에 사자를 배치하지 않는경우
    	dp[1][2] = 1; //첫번째 줄의 두번쨰 칸에 사자를 배치하지 않는경우
    	
    	
    	for(int i=2; i<N+1;i++) {
    		dp[i][0] = ( dp[i-1][0] + dp[i-1][1] + dp[i-1][2] ) % MOD;
    		dp[i][1] = ( dp[i-1][0] + dp[i-1][2] )% MOD;
    		dp[i][2] = ( dp[i-1][0] + dp[i-1][1] ) % MOD;
    	}
    	System.out.println( (dp[N][0] + dp[N][1] + dp[N][2] ) % MOD);
    	
    }
}

 

재귀와 메모이제이션을 활용합니다.

유의해야할점은 완료된 경우를 Coutning 할때는 경우가 1가지이기에 now가 마무리에 도착하면 1가지 경우로 Counting 합니다.

if(now == N-1) return 1;

 

또 이 문제가 왜 메모이제이션을 적용할 수 있을까요? 바로 최적 부분 구조가 성립되기 떄문입니다.

now 위치에서 다음 번에 check ( 0이면 XX, 1이면 OX, 혹은 XO )로 갈경우의 가지수를 반환한다. 라는 함수를 정의하여 사용합니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, L, R;
	static int answer = 0;
	static char[][] arr = new char[101][101];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		
//		10^5 * 4 * 2 = 128MB = 10^7 * 28
		N = Integer.parseInt(st.nextToken());
		for(int i=0;i<N; i++) {
			Arrays.fill(cache[i], -1);
		}
		answer = DFS(-1, 0) % MOD;
		System.out.println(answer );
	}
	
	static int[][] cache = new int[100001][2];
	static int MOD = 9901;
	static int DFS(int now, int check) {
		if(now == N-1) return 1;
		
		int ret = 0;
		if(now == -1) {
			ret = (DFS(now + 1, 0) + DFS(now + 1, 1) + DFS(now + 1, 1)) % MOD;
			return ret;
		}
		
		if(cache[now][check] != -1) return cache[now][check];
		if(check == 1) {
			ret = (DFS(now + 1, 1)  + DFS(now + 1, 0) % MOD);
		}else if(check == 0){
			ret += (DFS(now + 1, 1) + DFS(now + 1, 1) + DFS(now + 1, 0)) % MOD;
		}
 
		return cache[now][check] = ret;
	}
}

 

처음에 실패했던 코드입니다.

어떤 것이 문제였을까요? 바로 for문으로 다음 칸으로 넘어간다는 점입니다.

for문으로 다음칸으로 넘어간다면, 그 빈 공간 사이는 아무것도 하지않고 넘어가는 것이지요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, L, R;
	static int answer = 0;
	static char[][] arr = new char[101][101];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		for(int i=0;i<N; i++) {
			Arrays.fill(cache[i], -1);
		}
		answer = DFS(-1, false) % MOD;
		System.out.println(answer );
	}
	
	static int[][] cache = new int[100001][2];
	static int MOD = 9901;
	static int DFS(int now, boolean check) {
		if(now == N-1) return 1;
		
		int ret = 0;
		if(now == -1) {
			ret = (DFS(now + 1, false) + DFS(now + 1, true) + DFS(now + 1, true)) % MOD;
			return ret;
		}
		
		if(cache[now][check == true ? 1 : 0] != -1) return cache[now][check == true ? 1: 0];
//		10^5 * 4 * 2 = 128MB = 10^7 * 28
		for(int i=1; i<= N - now; i++) {
			if(i == 1)
				if(check == true) {
					ret = (DFS(now + i, true) + DFS(now + i, false) % MOD);
				}else if(check == false){
					ret += (DFS(now + i, true) + DFS(now + i, true) + DFS(now + i, false)) % MOD;
				}
			else {
				ret += (DFS(now + i, true) + DFS(now + i, true) + DFS(now + i, false)) % MOD;
			}
		}
		return cache[now][check == true ? 1 : 0] = ret;
	}
}