[백준] 다이어트 - Java 19942

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

 

 

 

문제를 보자마자 재료를 고르는 경우의 수를 비트마스킹으로 풀면 되겠다는 생각을 했다.

 

`3 <= N <= 15` 였기에 2^15 * N 이므로 문제의 제한시간인 2초에도 충분했다.

 

 

 

public class BOJ19942 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int minDan = Integer.parseInt(st.nextToken());
        int minFat = Integer.parseInt(st.nextToken());
        int minTan = Integer.parseInt(st.nextToken());
        int minVit = Integer.parseInt(st.nextToken());

        int[][] arr = new int[N][5];

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());

            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
            arr[i][3] = Integer.parseInt(st.nextToken());
            arr[i][4] = Integer.parseInt(st.nextToken());
        }

        int max = (1 << N);

        int minCost = Integer.MAX_VALUE;
        String resultSet = "-1";

        for(int i = 0; i < max; i++){
            int sumDan = 0;
            int sumFat = 0;
            int sumTan = 0;
            int sumVit = 0;
            int sumCost = 0;

            StringBuilder set = new StringBuilder();
            for(int j = 0; j < N; j++){
                if((i & (1 << j)) != 0){
                    sumDan += arr[j][0];
                    sumFat += arr[j][1];
                    sumTan += arr[j][2];
                    sumVit += arr[j][3];
                    sumCost += arr[j][4];

                    set.append((j + 1)).append(" ");
                }

            }

            if(minDan <= sumDan && minFat <= sumFat && minTan <= sumTan && minVit <= sumVit){
                if(minCost >= sumCost){
                    if(minCost == sumCost){
                        if(resultSet.compareTo(set.toString()) > 0){
                            resultSet = set.toString();
                        }
                    } else{
                        minCost = sumCost;
                        resultSet = set.toString();
                    }
                }
            }
        }

        if(minCost == Integer.MAX_VALUE){
            System.out.println(resultSet);
        } else{
            System.out.println(minCost);
            System.out.println(resultSet);
        }
    }
}