[백준/boj] 2620: 양팔저울 (Java) / DP / 배낭 문제

문제

2629번: 양팔저울

전체 코드 

import java.util.*;
import java.io.*;

public class Main_BOJ_2629_양팔저울 { // class 시작
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력 한줄 받아오기
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 출력을 위한 변수
	static StringTokenizer st; // 입력을 받아와서 공백 기준으로 분리하기 위한 변수
	static int N, M; // N: 추의 개수, M: 무게를 확인하고자 하는 구슬들의 개

	// dp[1]에는 주어진 추를 가지고 무게 1을 확인할 수 있는지 여부가 담겨있다.
	static boolean[] dp = new boolean[40001]; 
	
	static int max = 0; // 현재 확인할 수 있는 무게의 최댓값이 담길 것이다. 

	public static void main(String[] args) throws Exception { // main 시작
		N = Integer.parseInt(br.readLine()); // 추의 개수를 받아온다.

		// 오름차순으로 정렬된 추의 무게들을 라인 단위로 받는다. (*같은 무게 허용!!)
		st = new StringTokenizer(br.readLine()); 
		
		int value;
		for (int i = 0; i < N; i++) {
			value = Integer.parseInt(st.nextToken()); // 추의 무게를 작은 값부터 하나씩 가져온다.
			max = Math.max(value, max); // 더 무거운 무게로 계속 갱신
			
			// dp가 반복문 내에서 변경되지 않도록 temp 배열을 만든다. (*)
			boolean[] temp = new boolean[40001]; 
			
			// max가 반복문 내에서 변경되지 않도록 maxTemp를 만든다. (*)
			int maxTemp = max; 
			
			for (int n = 0; n <= max; n++) { // 현재 확인할 수 있는 가장 큰 무게까지 
				if (dp[n]) { // 만약 무게 n을 확인할 수 있다면
				
					// n 과 현재 받아온 추의 무게를 더한 무게와,
					temp[n + value] = true; 
			
					// n과 현재 받아온 추의 무게를 뺀 값의 절대값 무게는 확인할 수 있다.
					temp[Math.abs(value - n)] = true;  
					
					//  n 과 현재 받아온 추의 무게를 더한 무게는 max보다 클 것이다.
					// 확인할 수 있는 무게의 최댓값으로 계속해서 갱신한다. 
					maxTemp = Math.max(maxTemp, n + value); 
				}
			}
			max = maxTemp; // 현재 구할 수 있는 무게의 최댓 값으로 변경한다. 
			
			for (int j = 0; j <= max; j++) { // 현재 확인할 수 있는 가장 큰 무게까지  
			
				if (temp[j]) // 방금 위에서 추가된 확인할 수 있는 무게면  
					dp[j] = true; // dp배열도 true로 바꿔준다. 
			
			}
			
			dp[value] = true; // 위 과정이 끝나면, 받아온 추의 무게도 확인할 수 있다고 변경해준다. (*)
		}

		M = Integer.parseInt(br.readLine()); // 확인할 추의 개수 
		st = new StringTokenizer(br.readLine()); // 확인할 추의 무게들을 받아온다. 
		while (st.hasMoreTokens()) { // 모든 무게들을 받아올 때까지
			if (dp[Integer.parseInt(st.nextToken())]) { // 확인할 수 있는 무게이면 
				bw.append("Y "); // Y 출력 
			} else { // 확인 못하는 무게이면 
				bw.append("N "); // N 출력 
			}
		} 
		bw.flush();
		bw.close();
	} // main 끝
}// class 끝

(*)로 표시한 부분 풀이 

1. temp 배열을 만든 이유

int maxTemp = max; 
for (int n = 0; n <= max; n++) { // 현재 확인할 수 있는 가장 큰 무게까지 
	if (dp[n]) { // 만약 무게 n을 확인할 수 있다면
				
	// n 과 현재 받아온 추의 무게를 더한 무게와,
	temp[n + value] = true; 
			
	// n과 현재 받아온 추의 무게를 뺀 값의 절대값 무게는 확인할 수 있다.
	temp[Math.abs(value - n)] = true;  
	
	maxTemp = Math.max(maxTemp, n + value); 
	}
}

여기서 temp 없이 dp만 이용했다면, dp 가 실시간으로 바뀌게 된다. 그럼 바뀐 값에 대해서도 또 더하기, 빼기 연산을 하면서 확인할 수 없는 무게들도 true가 할당되게 된다. temp 배열을 이용하면 실시간으로 dp가 바뀌지 않기 때문에 확인할 수 있는 무게만 true로 변경된다. 

위 반복문을 거치면 확인할 수 있는 무게들이 추가 된다. 아래 반복문을 통해 dp도 true로 변경해준다. 

max = maxTemp; // 현재 구할 수 있는 무게의 최댓 값으로 변경한다. 
for (int j = 0; j <= max; j++) { // 현재 확인할 수 있는 가장 큰 무게까지  
			
	if (temp[j]) // 방금 위에서 추가된 확인할 수 있는 무게면  
		dp[j] = true; // dp배열도 true로 바꿔준다. 
			
}

이때, maxTemp의 역할은 2번에서 설명하겠다.

2. maxTemp의 역할

먼저, max에는 현재 확인할 수 있는 무게의 최댓값이 담겨져 있다.

만약 maxTemp를 안썼다고 가정해보자. 그럼 n+ value가 max보다 커서 max값을 갱신하고 난 후, n이 n++을 반복하다가 n+value의 값이 됐을 때, dp[(n+value)+n]도 true로 바뀌게 되고 max가 또 갱신되고 ••• 이 과정이 반복된다. 이를 방지하는게 maxTemp 이다!

maxTemp는 for문이 끝나면 확인할 수 있는 무게의 최댓값을 가지고 있을 것이다. 이를 max에 갱신 시켜주어 dp 배열을 true로 바꿔줄 때도 사용하고, 다음 추의 무게를 받아왔을 때에(value를 새로 받아왔을 때) 최대 무게까지 살펴볼 수 있도록 한다. 

3. 왜 value를 받아오고 dp[value] 를 바로 true로 바꿔주지 않는지?

이유는 간단한데, dp[value]를 true로 바꿔준 아래 for문을 실행하면

int maxTemp = max; 
for (int n = 0; n <= max; n++) { // 현재 확인할 수 있는 가장 큰 무게까지 
	if (dp[n]) { // 만약 무게 n을 확인할 수 있다면
				
	// n 과 현재 받아온 추의 무게를 더한 무게와,
	temp[n + value] = true; 
			
	// n과 현재 받아온 추의 무게를 뺀 값의 절대값 무게는 확인할 수 있다.
	temp[Math.abs(value - n)] = true;  
	
	maxTemp = Math.max(maxTemp, n + value); 
	}
}

dp[value]는 true기 때문에 if문 안으로 진입할 것이고, 이때 temp[value+ value] 를 true로 바꿔주게 된다. 예를 들어, 무게 4인 추가 들어왔을 때 무게 4인 추 하나로 8의 무게는 절대 구할 수 없다! 이러한 이유로 맨 마지막에 dp[value] = true 를 한다.

+ 추를 하나씩 받아오면서 확인할 수 있는 무게를 늘려가는게 배낭 문제와 풀이법이 비슷하다.