[백준] 19942: 다이어트 - JAVA

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

 

풀이

각 재료별로 단백질, 지방, 탄수화물, 비타민 함유량과 가격이 주어진다.

재료들을 혼합하여 영양분들을 더해 최소 영양분을 충족해야 한다.(최소 금액으로)

부분집합을 만들어 만들어진 집합에 대해 영양분들의 합이 만족하는지 판별해주었다.

비용이 이전의 비용보다 적은 경우에 갱신해주었고,

재료들의 번호를 출력해야 했기에 `TreeSet<String>` 을 선언하여 담았다.

이전의 최소 비용과 같은 경우에는 TreeSet에 추가만 해주었고,

이전 최소 비용보다 작은 값이여서 갱신이 필요한 경우엔 TreeSet을 새로 선언하여 추가하였다.

TreeSet은 사전 순으로 정렬되기 때문에 TreeSet의 `first()` 메소드를 이용해 답을 출력했다.

 

---

 

메모리: 37376KB
시간: 328ms
언어: Java 11

import java.io.*;
import java.util.*;

public class Main {
    static int n, mp, mf, ms, mv, cost;
    static int[][] table;
    static boolean[] selected;
    static TreeSet<String> group;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        mp = Integer.parseInt(st.nextToken());
        mf = Integer.parseInt(st.nextToken());
        ms = Integer.parseInt(st.nextToken());
        mv = Integer.parseInt(st.nextToken());

        table = new int[n + 1][5];
        for (int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 5; j++) {
                table[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        selected = new boolean[n + 1];
        cost = Integer.MAX_VALUE;
        group = new TreeSet<>();

        makeSet(1);

        if (group.size() > 0) {
            System.out.println(cost);
            System.out.println(group.first());
        } else {
            System.out.println(-1);
        }
    }

    private static void makeSet(int idx) {
        if (idx == n + 1) {
            calculate();
            return;
        }

        selected[idx] = true;
        makeSet(idx + 1);
        selected[idx] = false;
        makeSet(idx + 1);
    }

    private static void calculate() {
        int p = 0;
        int f = 0;
        int s = 0;
        int v = 0;
        int total = 0;

        for (int i = 1; i < n + 1; i++) {
            if (selected[i]) {
                p += table[i][0];
                f += table[i][1];
                s += table[i][2];
                v += table[i][3];
                total += table[i][4];
            }
        }

        if (p >= mp && f >= mf && s >= ms && v >= mv) {
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i < n + 1; i++) {
                if (selected[i]) {
                    sb.append(i + " ");
                }
            }
            if (cost > total) {
                cost = total;
                group = new TreeSet<>();
                group.add(sb.toString());
            } else if (cost == total) {
                group.add(sb.toString());
            }
        }
    }

}