19942번: 다이어트

문제

식재료 N개 중에서 몇 개를 선택해서 단백질, 지방, 탄수화물, 비타민의 합이 주어진 최소 영양소 기준을 만족하도록 할 때, 그 비용의 최솟값을 구하는 문제입니다. 조건을 만족하는 최소 비용 조합이 여러 개라면, 그중 사전 순으로 가장 빠른 것을 출력해야 합니다.

• 입력:
  • 첫째 줄: 식재료의 개수 N (3 ≤ N ≤ 15)
  • 둘째 줄: 단백질, 지방, 탄수화물, 비타민의 최소 요구량
  • 셋째 줄부터 N개의 줄: 각 식재료의 단백질, 지방, 탄수화물, 비타민, 가격
• 출력: 조건을 만족하는 최소 비용과 선택된 식재료 번호들을 오름차순으로 출력. 만족하는 경우가 없으면 -1 출력.

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

풀이 1: 비트마스킹 (Bitmasking)을 활용한 부분 집합 탐색

식재료의 최대 개수 N이 15로 매우 작기 때문에, 선택할 수 있는 모든 경우의 수(부분 집합)를 비트마스킹을 통해 탐색할 수 있습니다.

1. 모든 부분 집합 순회: 0부터 (1 << n) - 1까지 반복문을 돌며 모든 조합을 탐색합니다. 각 정수 i의 비트 상태가 하나의 식재료 조합을 의미합니다.
2. 영양소 및 비용 합산: 안쪽 반복문을 통해 (i & (1 << j)) != 0 인지 확인하여, j번째 식재료가 현재 조합에 포함되어 있다면 해당 식재료의 영양소와 비용을 누적 배열(sum)에 더합니다.
3. 최소 영양소 기준 검사: 누적된 4가지 영양소가 문제에서 주어진 최소 요구량을 모두 만족하는지 확인합니다.
4. 최소 비용 갱신 및 사전 순 판별:
   • 조건을 만족한다면 기존의 최소 비용(minCost)과 비교하여 더 작을 경우 정답을 갱신합니다.
   • 만약 비용이 동일하다면, 어떤 조합이 사전 순으로 앞서는지 판별(isLexicographicallySmaller)해야 합니다.
   • 단순히 작은 인덱스의 비트가 켜져있다고 앞서는 것이 아니기 때문에(예: {1}이 {1, 2}보다 사전 순으로 앞섬), 비트마스크 상태를 실제 리스트로 변환하여 앞에서부터 요소를 하나씩 비교하는 방식으로 정확한 사전 순 정렬을 보장합니다.

코드 1 (비트마스킹)

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

public class Main {
    static int n;

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

       int minCost = Integer.MAX_VALUE;
       int ans = -1;
       
       for (int i = 0; i < (1 << n); i++) {
          int[] sum = new int[5];
          for (int j = 0; j < n; j++) {
             if ((i & (1 << j)) != 0) {
                for (int k = 0; k < 5; k++) {
                   sum[k] += ingredients[j][k];
                }
             }
          }
          
          if (sum[0] >= minRequired[0] && sum[1] >= minRequired[1] && sum[2] >= minRequired[2] && sum[3] >= minRequired[3]) {
             if (minCost > sum[4]) {
                minCost = sum[4];
                ans = i;
             } else if (minCost == sum[4]) {
                if (isLexicographicallySmaller(i, ans)) {
                   ans = i;
                }
             }
          }
       }

       if (minCost == Integer.MAX_VALUE) {
          bw.write("-1");
       } else {
          bw.write(minCost + "\n");
          for (int i = 0; i < n; i++) {
             if ((ans & (1 << i)) != 0) {
                bw.write((i + 1) + " ");
             }
          }
       }

       bw.flush();
    }

    // 두 비트마스크 상태를 리스트로 변환하여 정확하게 사전 순 비교
    static boolean isLexicographicallySmaller(int current, int best) {
        List<Integer> listCur = new ArrayList<>();
        List<Integer> listBest = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if ((current & (1 << i)) != 0) listCur.add(i);
            if ((best & (1 << i)) != 0) listBest.add(i);
        }

        // 요소들을 차례대로 비교
        int minLen = Math.min(listCur.size(), listBest.size());
        for (int i = 0; i < minLen; i++) {
            if (!listCur.get(i).equals(listBest.get(i))) {
                return listCur.get(i) < listBest.get(i);
            }
        }

        // 겹치는 부분까지 모두 동일하다면, 길이가 더 짧은 쪽이 사전 순으로 앞섬 (예: {1} < {1, 2})
        return listCur.size() < listBest.size();
    }
}

풀이 2: 백트래킹 (DFS) 탐색

재귀를 사용하여 0번 식재료부터 '선택한다 / 선택하지 않는다'의 순서로 재귀 트리를 그려 탐색합니다. 비트마스킹과 달리 이 방식은 재귀 호출 순서에 의해 자연스럽게 사전 순으로 탐색이 이루어지기 때문에 복잡한 비교 로직 없이 사전 순 보장이 완벽히 처리됩니다.

1. 재귀 탐색: idx번째 식재료를 선택하는 경우와 선택하지 않는 경우로 나누어 dfs 함수를 재귀 호출합니다. 이때 사전 순으로 앞서는 결과를 먼저 찾기 위해 항상 '선택하는 경우'를 먼저 호출합니다.
2. 조건 확인 및 갱신: idx가 N에 도달하면 모든 식재료에 대한 선택 여부가 결정된 것입니다. 이때 누적된 영양소가 기준을 만족하고, 누적 비용 c가 minCost보다 엄격히 작을 때만(c < minCost) 최소 비용과 조합 리스트(bestCombination)를 갱신합니다.
3. 사전 순 보장: 비용이 같은 경우(c == minCost)에는 값을 갱신하지 않고 무시합니다. 이미 '선택하는 경우'를 먼저 탐색하는 재귀 트리를 구성했기 때문에, 나중에 발견된 동일 비용의 조합은 무조건 사전 순으로 뒤처지는 조합임이 수학적으로 보장됩니다.

코드 2 (백트래킹)

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

public class Main {
    static int n;
    static int[] minRequired = new int[4];
    static int[][] ingredients;
    static int minCost = Integer.MAX_VALUE;
    static List<Integer> bestCombination = null;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            minRequired[i] = Integer.parseInt(st.nextToken());
        }

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

        dfs(0, 0, 0, 0, 0, 0, new ArrayList<>());

        if (minCost == Integer.MAX_VALUE) {
            bw.write("-1\n");
        } else {
            bw.write(minCost + "\n");
            for (int i : bestCombination) {
                bw.write(i + " ");
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static void dfs(int idx, int p, int f, int s, int v, int c, List<Integer> selected) {
        // 모든 식재료를 탐색한 경우 영양소 기준 충족 여부 확인
        if (idx == n) {
            if (p >= minRequired[0] && f >= minRequired[1] && s >= minRequired[2] && v >= minRequired[3]) {
                // 비용이 더 낮을 때만 갱신 (비용이 같으면 먼저 탐색된 사전 순 정답을 유지)
                if (c < minCost) {
                    minCost = c;
                    bestCombination = new ArrayList<>(selected);
                }
            }
            return;
        }

        // 현재 식재료를 선택하는 경우 (사전 순으로 앞서기 위해 '선택' 분기를 먼저 탐색)
        selected.add(idx + 1);
        dfs(idx + 1, p + ingredients[idx][0], f + ingredients[idx][1], 
            s + ingredients[idx][2], v + ingredients[idx][3], c + ingredients[idx][4], selected);
        selected.remove(selected.size() - 1);

        // 현재 식재료를 선택하지 않는 경우
        dfs(idx + 1, p, f, s, v, c, selected);
    }
}

알고리즘 분류

브루트포스 알고리즘 (완전탐색), 비트마스킹 (Bitmasking), 백트래킹 (Backtracking)