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

문제링크

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

 

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main_2961 {

	static int N;
	static int S,B; //신맛 쓴맛
	static int sSum,bSum;
	static int min = Integer.MAX_VALUE;
	static ArrayList<int []> list = new ArrayList<>();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		for(int i=0;i<N;i++) {
			int S = sc.nextInt();
			int B = sc.nextInt();
			list.add(new int[] {S,B});
		}
		
		subset(1<<N);
		System.out.println(min);
	}
	
	public static void subset(int caseCount) {
		for(int flag=1;flag<caseCount;flag++) {
			sSum = 1;
			bSum = 0;
			for(int j=0;j<N;j++) {
				if((flag&1<<j)!=0) {
					//비트가 1이면
					int [] p = list.get(j);
					sSum *= p[0];
					bSum += p[1];
				}
			}
			min = min>Math.abs(sSum-bSum)?Math.abs(sSum-bSum):min;
		}
	}
}

 

 

이번에는 부분집합을 사용해서 풀 때 재귀를 사용안하고 비트마스킹을 사용해서 풀었다.

3진수를 예시로 들면

000

001

010

100

...

이런식으로 되니까 비트를 한 옆으로 옮기면서 비교하면서 비트가 1이면 selected되어서 들어가는 형식으로 풀었다.