백준 2960번: 도영이가 만든 맛있는 음식 [JAVA]

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

2961번: 도영이가 만든 맛있는 음식

• 풀이

부분집합을 이용한 문제이다.

재구함수로 각각의 재료를 쓰는 경우/안 쓰는 경우를 나눠 모든 부분집합을 구한 뒤, 각 부분집합에서의 쓴맛과 신맛 차이 중 가장 작은 값을 출력한다. 재료가 하나도 쓰이지 않은 경우는 제외한다.

• 코드

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

public class Main {
	static int N; // 재료의 수
	static int [] S, B; // 신맛과 쓴맛 배열
	static boolean [] isSelected; // 선택되었는지 안 되었는지
	static long minDiff; // 최소 차이
	
	static void subset(int num) {
		// 재귀 종료 조건
		if (num==N) {
			int s = 1; // 신맛
			int b = 0; //쓴맛
			int cnt = 0;
			for (int i=0; i<N; i++) {
				if (isSelected[i]==true) {
					cnt++;
					s *= S[i];
					b += B[i];
				}
			}
			if(cnt!=0) { // 재료가 0개가 아닌 경우
				int diff = Math.abs(s-b);
				if (diff<minDiff) minDiff = diff; // 최소 차이 갱신
			}
			return;
		}
		
		// 분할
		// 사용 O
		isSelected[num] = true;
		subset(num+1);
		
		// 사용 X
		isSelected[num] = false;
		subset(num+1);
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		// 재료 개수 입력
		N = Integer.parseInt(bf.readLine());
		S = new int[N];
		B = new int[N];
		isSelected = new boolean[N];
		
		// 신맛 쓴맛 입력
		for (int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			S[i] = Integer.parseInt(st.nextToken());
			B[i] = Integer.parseInt(st.nextToken());
		}
		
		minDiff = Integer.MAX_VALUE;
		subset(0);
		System.out.println(minDiff);
	}
}