[문제] 백준 2961번 도영이가 만든 맛있는 음식

www.acmicpc.net/problem/2961

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

풀이

 

간단한 조합 문제

public class BOJ_2961 {
	static int N;
	static int M;
	static int[][] material;
	static int total;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		
		material = new int[N][2];
		for(int i=0;i<N;i++) {
			StringTokenizer st = new StringTokenizer(in.readLine()," ");
			material[i][0] = Integer.parseInt(st.nextToken());
			material[i][1] = Integer.parseInt(st.nextToken());
		}
		total = Integer.MAX_VALUE;
		for(int i=1;i<=N;i++) {
			M = i;
			comb(0,new int[M],0);
		}
		System.out.println(total);
	}
	static void comb(int toSelect, int[] selected, int startIdx) {
		if(toSelect == M) {
			int sour = 1, bitter = 0;
			
			for(int i=0;i<M;i++) {
				int idx = selected[i];
				sour *= material[idx][0];
				bitter += material[idx][1];
			}
			int res = Math.abs(sour-bitter);
			total = Math.min(total, res);
			return;
		}
		for(int i=startIdx;i<N;i++) {
			selected[toSelect] = i;
			comb(toSelect+1, selected, i+1);
		}
	}
}