boj19942 다이어트

링크

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

문제

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

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

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

입력

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

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

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

출력

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

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

나의 풀이

• 먼저 음식정보를 저장할 Food 클래스를 생성했다.
• 중복 탐색을 줄이기위해 현재 배열의 위치보다 뒤 위치의 배열을 탐색하는 식으로 탐색하였다.
• 기준을 모두 넘기는 선택지가 주어지면 먼저, minCost를 체크한다.
  • 이때, minCost 현재 선택된 cost 보다 더 크면, finalchecklist 에 checked 배열을 복사하고 넘어간다.
  • minCost 가 현재 선택된 cost 와 같으면 for 문을 돌면서 checked 배열에서 true 인 요소가 finalchecklist 에서 true 인 요소보다 사전상 더 작은 숫자인지 체크한다.
    • 예를 들면, 같은 cost 값을 갖더라도, 3 보다 1 2 3 이 답인 것이 사전상 더 앞이다.
• 핵심 코드

  private static void dfs(boolean[] checked, Food infos,int now){
          if(infos.checkStandard(standard)){
              if(minCost>infos.c){
                  minCost = infos.c;
                  finalchecklist=Arrays.copyOf(checked,N);
              }else if(minCost==infos.c){
                  for (int i = 0; i < N; i++) {
                      if(finalchecklist[i]&&!checked[i]) break;
                      if(checked[i]&&!finalchecklist[i]){
                          finalchecklist = Arrays.copyOf(checked,N);
                          break;
                      }
                  }
              }
              return;
          }
          for (int i = now+1; i < N; i++) {
              if(checked[i]) continue;
              checked[i] = true;
              infos.addNutri(foods[i]);
              dfs(checked,infos,i);
              infos.minusNutri(foods[i]);
              checked[i] = false;
          }
      }
  }

• 전체 코드

  package Baekjoon.java.gold;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.List;
  import java.util.StringTokenizer;
  
  public class boj19942 {
  
      static class Food{
          private int p;
          private int f;
          private int s;
          private int v;
          private int c;
  
          public Food(int p, int f, int s, int v, int c) {
              this.p = p;
              this.f = f;
              this.s = s;
              this.v = v;
              this.c = c;
          }
  
          public boolean checkStandard(int[] standard){
              if(p<standard[0]){
                  return false;
              }else if(f<standard[1]){
                  return false;
              }else if(s<standard[2]){
                  return false;
              }else if(v<standard[3]){
                  return false;
              }
              return true;
          }
  
          public void addNutri(Food food){
              p+=food.p;
              f+=food.f;
              s+=food.s;
              v+=food.v;
              c+=food.c;
          }
          public void minusNutri(Food food){
              p-=food.p;
              f-=food.f;
              s-=food.s;
              v-=food.v;
              c-=food.c;
          }
  
      }
      static int N;
      static boolean[] checked;
      static boolean[] finalchecklist;
      static int minCost;
      static int[] standard;
      static Food[] foods;
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          standard = new int[4];
  
          N = Integer.parseInt(br.readLine());
          checked = new boolean[N];
          finalchecklist = new boolean[N];
  
          minCost=Integer.MAX_VALUE;
          StringTokenizer st = new StringTokenizer(br.readLine());
          for (int i = 0; i < 4; i++) {
              standard[i] = Integer.parseInt(st.nextToken());
          }
  
          foods = new Food[N];
          for (int i = 0; i < N; i++) {
              st = new StringTokenizer(br.readLine());
              int p = Integer.parseInt(st.nextToken());
              int f = Integer.parseInt(st.nextToken());
              int s = Integer.parseInt(st.nextToken());
              int v = Integer.parseInt(st.nextToken());
              int c = Integer.parseInt(st.nextToken());
              foods[i] = new Food(p,f,s,v,c);
          }
          dfs(checked,new Food(0,0,0,0,0),-1);
          if(minCost==Integer.MAX_VALUE){
              System.out.println(-1);
          }else{
              System.out.println(minCost);
              for (int i = 0; i < N; i++) {
                  if(finalchecklist[i]){
                      System.out.print((i+1)+" ");
                  }
              }
          }
      }
  
      private static void dfs(boolean[] checked, Food infos,int now){
          if(infos.checkStandard(standard)){
              if(minCost>infos.c){
                  minCost = infos.c;
                  finalchecklist=Arrays.copyOf(checked,N);
              }else if(minCost==infos.c){
                  for (int i = 0; i < N; i++) {
                      if(finalchecklist[i]&&!checked[i]) break;
                      if(checked[i]&&!finalchecklist[i]){
                          finalchecklist = Arrays.copyOf(checked,N);
                          break;
                      }
                  }
              }
              return;
          }
          for (int i = now+1; i < N; i++) {
              if(checked[i]) continue;
              checked[i] = true;
              infos.addNutri(foods[i]);
              dfs(checked,infos,i);
              infos.minusNutri(foods[i]);
              checked[i] = false;
          }
      }
  }

결과