1127 : 맛있는 음식(PERKET)

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=407&sca=40

JUNGOL | 맛있는 음식(PERKET) > 문제은행

재료가 조합될 수 있는 모든 경우의 수를 완탐해보고 최소값을 구해보면 된다.

재료의 조합을 구할 때는 전체 요소를 이용한 부분집합 만드는 방법을 이용해보자.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**************************************************************
 * Problem: 1127
 * User: itsmeyjc
 * Language: Java
 * Result: Success
 * Time:99 ms
 * Memory:8776 kb
 * http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=407&sca=40
 ****************************************************************/
public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new StringReader(Main.src));
		int n = Integer.parseInt(br.readLine());
		List<int[]> materials = new ArrayList<>();
		StringTokenizer tokens = null;
		for (int i = 0; i < n; i++) {
			tokens = new StringTokenizer(br.readLine());
			materials.add(new int[] { Integer.parseInt(tokens.nextToken()), Integer.parseInt(tokens.nextToken()) });
		}
		int answer = Integer.MAX_VALUE;
		List<Integer> subset = null;
		for (int i = 1; i < (1 << n); i++) {
			int sumS = 1;
			int sumB = 0;

			subset = new ArrayList<>();
			// subset 준비 완료
			for (int j = 0; j < n; j++) {
				if ((i & (1 << j)) > 0) {
					subset.add(j);
				}
			}
			//System.out.println("subset: " + subset);
			// subset 내용으로 맛 계산
			for (int j = 0; j < subset.size(); j++) {
				int[] sub = materials.get(subset.get(j));
				//System.out.println("재료 구성: " + Arrays.toString(sub));
				sumS *= sub[0];
				sumB += sub[1];
			}
			int result = Math.abs(sumS - sumB);
			//System.out.println(result);
			if (result == 0) {
				answer = 0;
				break;
			} else {
				if (answer > result) {
					answer = result;
				}
			}
		}
		System.out.println(answer);
	}

	static String src = "4\r\n" +
						"1 7\r\n" +
						"2 6\r\n" +
						"3 8\r\n" +
						"4 9";

}