백준 17610번: 양팔저울

문제 설명

• https://www.acmicpc.net/problem/17610
• k개의 추로 만들 수 없는 무게의 개수를 구하는 문제입니다.

접근법

• 추를 활용하는 방법은 추를 물건 반대편에 놓는다, 추를 물건과 함께 놓는다, 추를 안놓는다 3 가지 경우의 수만 존재합니다.
• k가 13으로 작아 완전탐색이 가능하다 생각했습니다.(3^13<1_000_000)
• 부분집합으로 문제를 풀었습니다.

정답

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

public class Main {
	static boolean[] v;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] num = new int[N];
		int maxVal = 0;
		for (int i = 0; i < N; i++) {
			num[i] = sc.nextInt();
			maxVal += num[i];
		}
		v = new boolean[maxVal + 1];

		subset(0, N, num, new int[N]);
		int score = 0;
		for (int i = 1; i <= maxVal; i++) {
			if (!v[i])
				score++;
		}
		System.out.println(score);
	}

	public static void subset(int depth, int N, int[] num, int[] answer) {
		if (depth == N) {
			int sum = 0;
			for (int i = 0; i < N; i++) {
				sum += answer[i];
			}
			if (sum <= 0) return; // 합이 음수인 경우는 제외
			v[sum] = true;
			return;
		}

		answer[depth] = num[depth];
		subset(depth + 1, N, num, answer);

		answer[depth] = -num[depth];
		subset(depth + 1, N, num, answer);

		answer[depth] = 0;
		subset(depth + 1, N, num, answer);

	}
}