[백준] 2629 양팔저울 - DP(Dynamic Programming) + 냅색(Knapsack, 배낭문제) JAVA

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

2629번: 양팔저울

코드설명

DP(Dynamic Programming) + 냅색(Knapsack, 배낭문제) 문제 입니다.

 

이 문제에서 DP[31][30*500 + 1] 은 구슬의 개수가 30개를 사용했을때 15001 개의 배열 중에서 결론적으로 잴 수 있는 무게인지 아닌지의 참/거짓이 저장됩니다.

 

문제에서 무게를 잴 구슬을 항상 양팔 저울 중에서 왼쪽 저울에 둔다고 가정해보겠습니다.

DFS(level + 1, weight + arr[level])  : 오른쪽저울에 추를 둡니다.

DFS(level + 1, weight); : 오른쪽 저울에 아무것도 두지 않습니다.

DFS(level + 1, Math.abs(weight - arr[level])); : 왼쪽 저울에 추를 올립니다.

위와 같이 진행하면 DP[N][15001] 의 N번쨰 배열은 결국 모든 무게의 가능여부를 확인할 수 있습니다.

 

if(dp[N][K] == true) 

위와 같이 잴 수 있는 구슬의 무게를 구할때 DP[N][~] 에서 N번째 배열을 확인하는 이유는 N번째에 모든 경우를 다 탐색하는것이기 때문입니다. 그전에도 for문으로 DP의 모든 경우를 돌면서 가능한 경우가 하나라도 있다면 하는방법으로 체크해도 되지만 그렇게 할경우 시간복잡도로 시간초과가 날 것 입니다.

 

문제에서 유의해야할점은, 최대 추의 개수는 30 이하이고, 추의 무게는 500g 이하이기 떄문에 최대 추로 잴 수 있는 무게는 30 * 500 으로 15000 입니다.

하지만, 확인하고자하는 구슬의 무게는 40,000 보다 작거나 같기에 dp[N][30 * 500 + 1] 로 해놓았기에 런타임 에러 (ArrayIndexOutOfBounds) 가 발생하는데, 아래와 같이 continue 구문을 추가하거나 if esle if else if 로 처리하여 초과된 구슬의 무게일경우 로직이 검증하지 않도록 처리해줍니다.

for(int i=0;i<M;i++) {
    int inputMarbleWeight = Integer.parseInt(st.nextToken());

    if(inputMarbleWeight > 15000) {
        System.out.print("N ");
        continue;
    }
    if(dp[N][inputMarbleWeight] == true) {
        System.out.print("Y ");
    }else {
        System.out.print("N ");
    }

}

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static int[] arr = new int[31];
	public static boolean[][] dp = new boolean[31][30*500 + 1];
	public static StringBuilder sb = new StringBuilder();
	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());
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());   	
		}
    	//여기서 미리 DP로 가능한 경우의 모든 수를 구한다.
    	DFS(0, 0);
    	
    	st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	for(int j=0;j<M;j++) {
    		
    		int K = Integer.parseInt(st.nextToken());
    		if(K > 15000) sb.append("N ");
    		else if(dp[N][K] == true) {
    			sb.append("Y ");
    		}else {
    			sb.append("N ");
    		}
    	}
    	System.out.println(sb.toString());
	}
	
	public static void DFS(int level, int weight) {
		if(dp[level][weight] == true) return ;
		dp[level][weight] = true;
		if(level == N) return ;
		
		DFS(level + 1, weight + arr[level]);
		DFS(level + 1, weight);
		DFS(level + 1, Math.abs(weight - arr[level]));
		
	}
	
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static Marble[] marble;
	public static boolean[][] dp;
	public static int answer = 0;
	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());
		marble = new Marble[31];
		dp = new boolean[31][30 * 500 + 1];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			int inputMarbleWeight = Integer.parseInt(st.nextToken());
			marble[i] = new Marble(inputMarbleWeight);
		}
		
		simulate(0,0);
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<M;i++) {
			int inputMarbleWeight = Integer.parseInt(st.nextToken());
			
			if(inputMarbleWeight > 15000) {
				System.out.print("N ");
				continue;
			}
			if(dp[N][inputMarbleWeight] == true) {
				System.out.print("Y ");
			}else {
				System.out.print("N ");
			}
			
		}
	}
	
	public static void simulate(int level, int weight) {
		if(dp[level][weight] == true) return ;
		dp[level][weight] = true;
		if(level >= N) return ;
		
		simulate(level + 1, weight + marble[level].weight);
		simulate(level + 1, weight);
		simulate(level + 1, Math.abs(weight - marble[level].weight));
	}
	
}

class Marble{
	int weight;
	public Marble(int weight) {
		this.weight = weight;
	}
}