백준 - 2691 : 도영이가 만든 맛있는 음식 [자바]

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

public class Main {
	// 재료 N개
	// 각 재료의 신맛 S, 쓴맛 B
	// 음식의 신맛 = 재료의 신맛 곱하기
	// 음식의 쓴맛 = 재료의 쓴맛 더하기
	// 음식의 신맛과 쓴맛 차이 작게 만들기
	// 물을 제외하고 재료 1개 이상 사용하기
	// 결과 : 신맛과 쓴맛의 차이가 가장 작은 요리 만들기
	static int[] numbers[];
	static int[][] ingredients;
	static boolean[] isSelected;
	static int N, result; // 재료의 개수

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();

		// 재료의 개수
		N = Integer.parseInt(br.readLine());
		result = Integer.MAX_VALUE;

		// 재료 담을 2차원 배열
		ingredients = new int[N][2];
		// 재료의 신맛[][0], 쓴맛[][1]
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			ingredients[i][0] = Integer.parseInt(st.nextToken());
			ingredients[i][1] = Integer.parseInt(st.nextToken());
		}

		isSelected = new boolean[N]; // 재료 선택 확인용
		// 부분집합
		SubSet(0);
		sb.append(result);
		System.out.println(sb);
	}

	// 부분집합
	static void SubSet(int cnt) {
		if (cnt == N) {
			int s_sum = 1; // 신맛 합, 곱하기 해야하니까 초기값 1
			int b_sum = 0; // 쓴맛 합
			for (int i = 0; i < ingredients.length; i++) {
				if (isSelected[i]) {// 재료가 선택되었으면
					s_sum *= ingredients[i][0];
					b_sum += ingredients[i][1];
				}
			}
			if (b_sum != 0) {
				// 재료를 한 가지 이상 써야하는데 부분집합은 공집합도 포함
				// 신맛과 쓴맛이 양의 정수이므로, 1~
				// 신맛이 1인 경우 1*1로 공집합인 경우와 구분 불가
				// 쓴맛은 재료를 한 가지 이상 쓰면 무조건 0보다 크므로 b_sum!=0인 경우로 체크
				int diff = Math.abs(s_sum - b_sum);
				if (result > diff) result = diff;
			}
			return;
		}
		isSelected[cnt] = true;
		SubSet(cnt + 1);

		isSelected[cnt] = false;
		SubSet(cnt + 1);
	}
}