백준 2961 도영이가 만든 맛있는 음식

www.acmicpc.net/problem/2961

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

---

부분집합 (power set)을 이용하여 풀이

재료를 고르고 = true

고르지않고 = false

---

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class 도영이가만든맛있는음식 {
	public static class Menu{
		 int S;//신맛
		 int B;//쓴맛

		public Menu(int s, int b) {
			super();
			S = s;
			B = b;
		}

		@Override
		public String toString() {
			return "Menu [S=" + S + ", B=" + B + "]";
		}	
	}
	static int N;
	static Menu [] menus;//재료를담을객체배열
	static int res;//가장 작은 신맛쓴맛 차이
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/도영이가만든맛있는음식.txt"));
		Scanner sc = new Scanner(System.in);
		N =sc.nextInt();//재료의개수
		menus = new Menu[N];
		res = Integer.MAX_VALUE;//가장작은차이 출력이므로 max값으로초기화
		for (int i = 0; i < N; i++) {
			menus[i] = new Menu(sc.nextInt(), sc.nextInt());
//			System.out.println(menus[i].toString());
		}
		select(new boolean[N],0,0);//방문배열, 인덱스값, 뽑은값
		System.out.println(res);//최소 차이 출력
	}
	/*
	 * 신맛 S(곱) 쓴맛 B(합) 
	 * 신맛과 쓴맛의 차이를 최대한작게. //신맛합Ssum 쓴맛합Bsum 제일차이적은 신맛쓴맛 resS resB
	 *  재료 적어도 하나이상사용(공집합은안돼). 
	 * N 재료개수 N개줄에 신맛 쓴맛 ,  
	 */
	private static void select( boolean[] sel, int idx,int k) {
		if(idx == menus.length ) {
			int Ssum=1;//신맛곱의 합
			int Bsum=0;//쓴맛 합
			int temp=0;//신맛쓴맛 차이를 저장할 변수
			int cnt=0;//최소 한번이상은 수행되어야함
			for (int i = 0; i < sel.length; i++) {
				if(sel[i]) {//그 인덱스가 false가 아니라면
					Ssum *= menus[i].S;//신맛은 곱한값
					Bsum += menus[i].B;//쓴맛은 더한값
					cnt++;
				}
			}
			temp = Math.abs(Ssum - Bsum);//신맛과 쓴맛의 차이를 저장
			if(cnt>=1 && res>temp) {//한번이상 수행되어졌고 기존 res값보다 temp값이 작다면 업데이트.
				//System.out.println(Ssum +" "+ Bsum);
				res = temp;
			}
		return;
		}
		sel[idx]=true;
		select(sel, idx+1, k+1);
		sel[idx]=false;
		select(sel, idx+1, k);
	}

}