[BOJ/Java] 2961 도영이가 만든 맛있는 음식

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

public class Main {

	static int n, sour = 1, bitter, minDiff = Integer.MAX_VALUE, tmpDiff;
	static int[][] pairs;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		pairs = new int[n][2];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			pairs[i] = new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) };
		}
		for (int r = 1; r <= n; r++) {
			combination(0, 0, r);
		}
		System.out.println(minDiff);
	}

	private static void combination(int cnt, int start, int r) {
		if (cnt == r) {
			tmpDiff = Math.abs(sour - bitter);
			if (tmpDiff < minDiff) {
				minDiff = tmpDiff;
			}
			return;
		}
		for (int i = start; i < n; i++) {
			sour *= pairs[i][0];
			bitter += pairs[i][1];
			combination(cnt + 1, i + 1, r);
			sour /= pairs[i][0];
			bitter -= pairs[i][1];
		}
	}
}

조합의 합이 어차피 부분 집합이니까 간단하게 작성한 코드

bit masking으로 다시 풀어보자

 

비트 마스킹 + 부분 집합 버전

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

public class Main {

	static int n, sour, bitter, minDiff = Integer.MAX_VALUE, i;
	static int[][] pairs;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		pairs = new int[n][2];
		for (i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			pairs[i] = new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) };
		}
		subSet(0, 0);
		System.out.println(minDiff);
	}
    
	private static void subSet(int cnt, int flag) { // selected 배열 대신 flag를 통해 사용 여부 체크
		if (cnt == n) {
			if (flag == 0) // 아무것도 선택하지 않는 경우 즉, flag = 0일 때
				return;
			sour = 1;
			bitter = 0;
			for (i = 0; i < n; i++) {
				if ((flag & 1 << i) != 0) {
					sour *= pairs[i][0];
					bitter += pairs[i][1];
				}
			}
			minDiff = Math.min(Math.abs(sour - bitter), minDiff);
			return;
		}
		subSet(cnt + 1, flag | 1 << cnt); // cnt depth만큼 bit shift 수행해서 선택 여부 check
		subSet(cnt + 1, flag); // 선택하지 않는 경우의 수도
	}
}