[B2961][도영이가 만든 맛있는 음식][java]

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

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

 

 

풀이

재료 n개, 각 재료의 신맛 S, 쓴맛 B

여러 재료로 요리할 때,
신맛 = 사용한 재료들의 신맛의 곱
쓴맛 = 사용한 재료들의 쓴맛의 합

신맛과 쓴맛의 차이를 적게, 재료는 적어도 하나 사용

 

코드

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

// 문제를 보자마자 부분 집합을 구하는 문제가 떠오르고 비트마스킹이 생각났다.
// 비트마스킹으로 구하는 건 이제 잘 떠오른다. 뿌듯.
public class Main {
    public static class Ingredient {
        int s, b;

        public Ingredient(int s, int b) {
            this.s = s;
            this.b = b;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Ingredient> ingredients = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            ingredients.add(new Ingredient(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        int answer = Integer.MAX_VALUE;
        for (int i = 1; i < Math.pow(2, n); i++) {
            List<Ingredient> list = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) list.add(ingredients.get(j));
            }
            answer = Math.min(answer, cal(list));
        }

        System.out.println(answer);
    }
    
    public static int cal(List<Ingredient> list){
        int s = 1, b = 0;
        for (Ingredient ingredient : list) {
            s *= ingredient.s;
            b += ingredient.b;
        }
        
        return Math.abs(s - b);
    }
}