[백준, BOJ 17610] 양팔저울 (java)

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

17610번: 양팔저울

---

문제

무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고 그 무게가 각각 {1, 2, 6}이면, S = 9이고, 양팔 저울을 한번만 이용하여 1부터 S사이 모든 정수에 대응하는 물을 다음과 같이 그릇에 담을 수 있다. 여기서, X는 그릇에 담는 물의 무게를 나타내고, □는 그릇을 나타낸다.

X	1	2	3	4	5	6	7	8	9
	□:1	□:2	□:(1+2)	(□+2):6	(□+1):6	□:6	□:(1+6)	□:(2+6)	□:(1+2+6)

만약 추의 무게가 {1, 5, 7}이면 S = 13이 되고, 양팔저울을 한 번만 사용하여 그릇에 담을 수 있는 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이다. 즉, 1부터 S사이 수 가운데 9와 10에 대응하는 무게의 물을 그릇에 담는 것은 불가능하다.

k(3 ≤ k ≤ 13)개 추 무게 $g_1, g_2, ..., g_k$가 주어질 때, 1부터 S사이에 있는 정수 중, 양팔 저울을 한번만 이용하여서는 측정이 불가능한 경우의 수를 찾는 프로그램을 작성하고자 한다.

입력

입력의 첫 줄에는 추의 개수를 나타내는 정수 k(3 ≤ k ≤ 13)가 주어진다. 다음 줄에는 k개의 정수 $g_i(1 \le g_i \le 200,000)$가 공백으로 구분되어 주어지는데 이는 각 추의 무게를 나타낸다.

출력

1부터 S(추 무게의 합) 사이에 있는 정수 중, 양팔 저울을 한번만 이용해서는 측정이 불가능한 경우의 수를 출력한다.

728x90

 

예제 입력 1

3
1 5 7

예제 출력 1

2

---

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

public class Main {
	
	static int[] weight;
	static boolean[] arr;

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// k 입력, 추의 무게를 담는 weight 배열 생성
		int k = Integer.parseInt(br.readLine());
		weight = new int[k];
		
		// 추의 무게 입력, 추의 모든 무게를 합한 크키 + 1 만큼의 배열 arr 생성
		// arr 배열에 인덱스에 해당하는 무게를 구할 수 있는지 boolean 타입으로 체크
		st = new StringTokenizer(br.readLine());
		int sum = 0;
		for (int i = 0; i < k; i++) {
			weight[i] = Integer.parseInt(st.nextToken());
			sum += weight[i];
		}
		arr = new boolean[sum + 1];
		
		// 측정
		estimate(0, 0);
		
		
		// 측정 불가능한 수 출력
		int result = 0;
		for (int i = 1; i < sum + 1; i++) {
			if (arr[i] == false)
				result++;
		}
		System.out.print(result);
	}

	static void estimate(int w, int idx) {
		if(idx < weight.length) {
			// 현재 무게를 포함하지 않음
			estimate(w, idx + 1);
			// 현재 무게를 왼쪽 저울에 포함함.
			estimate(w - weight[idx], idx + 1);
			// 현재 무게를 오른쪽 저울에 포함함.
			estimate(w + weight[idx], idx + 1);
		}
		
		// 마지막 추의 포함 여부까지 확인했으며, w이 양수라면
		// 무게 w는 측정 가능한 수 이므로 arr를 true로 바꿔준다.
		if(idx == weight.length && w > 0) {
			arr[w] = true;
		}
	}
}