[PS] BOJ 19942 - 다이어트

문제 설명

식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각해보자. 이 경우 모든 재료를 선택하면 쉽게 해결되지만, 우리는 조건을 만족시키면서도 비용이 최소가 되는 선택을 하려고 한다.

재료	단백질	지방	탄수화물	비타민	가격
1	30	55	10	8	100
2	60	10	10	2	70
3	10	80	50	0	50
4	40	30	30	8	60
5	60	10	70	2	120
6	20	70	50	4	40

예를 들어, 식재료 1, 3, 5를 선택하면 영양분은 100, 145, 130, 10으로 조건을 만족하지만 가격은 270이 된다. 대신 2, 3, 4를 선택하면 영양분의 합은 110, 130, 90, 10, 비용은 180이 되므로, 앞의 방법보다는 더 나은 선택이 된다.

입력으로 식재료 표가 주어졌을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.

입력

첫 줄에 식재료의 개수 $N$이 주어진다.

다음 줄에는 단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 나타내는 정수 $mp$, $mf$, $ms$, $mv$가 주어진다.

이어지는 $N$개의 각 줄에는 $i$번째 식재료의 단백질, 지방, 탄수화물, 비타민과 가격이 5개의 정수 $p_i$, $f_i$, $s_i$, $v_i$, $c_i$와 같이 주어진다. 식재료의 번호는 1부터 시작한다.

출력

첫 번째 줄에 최소 비용을 출력하고, 두 번째 줄에 조건을 만족하는 최소 비용 식재료의 번호를 공백으로 구분해 오름차순으로 한 줄에 출력한다. 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다.

조건을 만족하는 답이 없다면 -1을 출력하고, 둘째 줄에 아무것도 출력하지 않는다.

풀이

이 문제를 풀기 전에 문제를 먼저 풀어보는 것을 추천한다.

위 문제와 큰 틀은 같다.

식재료를 선택하거나 안하거나 두가지의 경우의 수가 있고, 각 식재료를 선택 시 다시 다음 식재료에 대해 두가지 경우의 수를 탐색하는 방식의 dfs 로 풀면된다.

문제와 가장 큰 차이점은 최소값을 구하는 것 뿐만 아니라 조건을 만족하는 최소 비용 식재료의 번호도 출력해야 한다는 것이다. 이 조건으로 인해 백트래킹 로직이 필요하다.

또한, 입력으로 들어오는 값의 범위가 다르다. 이번 문제에서는  $0\le p_i,f_i,s_i,v_i,c_i\le 500$  라는 제한 범위가 있는데, 만약 모든 영양소가 0 0 0 0 0 이렇게 입력되는 경우에는 정답으로 카운트하지 않아야 한다. 아래와 같이 입력되는 경우 맨 첫번째 재료만 카운트하고 dfs 를 종료해야 한다.

3
0 0 0 1
0 0 0 1 1
0 0 0 0 0
0 0 0 0 0

// answer
1
1

실버문제 풀때와 같이 dfs 의 탈출 조건을 아래처럼 idx == N 로 설정하게 되면 위 예외 케이스의 경우 정답과 다른 결과가 나오게 된다.

if (idx == N) { // 모든 범위 순회 후 조건을 검사하는 경우 엣지 케이스까지 정답에 포함시킬 수 있다.
  if (p >= mp && f >= mf && s >= ms && v >= mv) {
    if (c < min) {
      min = c;
      result = new ArrayList<>(tmpResult);
    }
  }
  return;
}

코드

import java.util.ArrayList;

public class Boj_19942 {
  static int N;
  static ArrayList<int[]> arr;
  static int mp, mf, ms, mv;
  static int min = Integer.MAX_VALUE;
  static ArrayList<Integer> result = new ArrayList<>();
  static ArrayList<Integer> visited = new ArrayList<>();

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

    String[] split = br.readLine().split(" ");
    mp = Integer.parseInt(split[0]);
    mf = Integer.parseInt(split[1]);
    ms = Integer.parseInt(split[2]);
    mv = Integer.parseInt(split[3]);

    for (int i = 0; i < N; i++) {
      String[] nutrient = br.readLine().split(" ");
      arr.add(new int[] {Integer.parseInt(nutrient[0]), Integer.parseInt(nutrient[1]), Integer.parseInt(nutrient[2]),
        Integer.parseInt(nutrient[3]), Integer.parseInt(nutrient[4])});
    }

    dfs(0, 0, 0, 0, 0, 0);

    if (min == Integer.MAX_VALUE) {
      System.out.println(-1);
    } else {
      System.out.println(min);
      for (Integer i : result) {
        System.out.print(i + " ");
      }
    }
  }

  private static void dfs(int idx, int p, int f, int s, int v, int c) {
    if (p >= mp && f >= mf && s >= ms && v >= mv) {  // 조건 만족시 바로 리턴
      if (c < min) {
        min = c;
        result = new ArrayList<>(visited);
        return;
      }
    }

    if (idx == N) {
      return;
    }

    visited.add(idx + 1);
    dfs(idx + 1, p + arr.get(idx)[0], f + arr.get(idx)[1], s + arr.get(idx)[2], v + arr.get(idx)[3], c + arr.get(idx)[4]);
    visited.remove(visited.size() - 1);  // 백트래킹

    dfs(idx + 1, p, f, s, v, c);
  }

}