[백준 2629번] 양팔저울

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

 

 

 

해당 문제에 대한 조건을 풀어서 작성한다면?

1. 추의 개수 <= 30
2. 추의 무게 <= 500
3. 전체 추의 무게를 합했을 경우 15 * 10^3
4. 확인할 구슬의 개수 <= 7
5. 각각 구슬의 무게 <= 4 * 10^4

단순하게 brute-force로 진행할 경우, 1.4 * 10^10으로 시간 초과가 날 것이다.

 

다른 사람들의 풀이를 보니, DP를 사용하거나, 재귀호출을 활용한 DFS를 이용하여 풀었다. -> 추의 개수가 최대 30개, 무게가 40,000이므로 int[][] arr = new int[31][40001]에 대하여,,,

 

자료구조를 활용한 나의 풀이

나 같은 경우, Set함수를 활용해서, 추를 통해 만들 수 있는 무게들을 저장해주었다.

Set을 활용할 경우, 중복되는 무게는 담기지 않는다.

 

• 다음과 같이, 기존 무게에서 추가로 추를 더하거나 기존에 만들 수 있는 무게들의 총합에서 현재 추를 빼서 만들 수 있는 무게들을 만들어줬다.
• 마지막에는 자기 자신만의 추를 더해주었다.
• 다음과 같이 할 경우, N <= 30, 전체 무게의 합은 40,000을 넘지 않으므로 최대 30 * 40000 ~= 1,200,000 번 정도의 반복 연산이 실행될 것이다.

현재 코드에서 조금 다른 점은 따로 next라는 Set 자료구조를 하나 더 생성하고, 추가된 무게의 합을 weight 에 addAll을 하는 것인데, 이부분은 ConcurrentModificationException 예외가 발생에 따라서 다음과 같이 진행했다.

 

https://moon-code.tistory.com/entry/ConcurrentModificationException-%EC%98%88%EC%99%B8-%EA%B4%80%EB%A0%A8

ConcurrentModificationException 예외 관련

 

 

// 주어진 추를 이용하여 만들 수 있는 무게들을 저장한 Set
Set<Integer> weight = new HashSet<>();

		for (int i = 0; i < N; i++) {
			Set<Integer> next = new HashSet<>();
			for (Integer w : weight) {
				next.add(w + arr[i]);
				next.add(Math.abs(w - arr[i]));
			}
			next.add(arr[i]);
			weight.addAll(next);
		}

 

 

다음은 전체 풀이 코드이다.

 

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

public class BOJ_G3_2629_양팔저울 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Set<Integer> weight = new HashSet<>();

		for (int i = 0; i < N; i++) {
			Set<Integer> next = new HashSet<>();
			for (Integer w : weight) {
				next.add(w + arr[i]);
				next.add(Math.abs(w - arr[i]));
			}
			next.add(arr[i]);
			weight.addAll(next);
		}

		int T = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());

		while (T-- > 0) {
			// 구하고자하는 추의 무게
			int W = Integer.parseInt(st.nextToken());

			if (weight.contains(W)) sb.append("Y ");
			else sb.append("N ");
		}

		System.out.println(sb);
	}
}