백준 19942 다이어트 [JAVA]

문제

식재료 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개의 정수 pi, fi, si, vi, ci와 같이 주어진다. 식재료의 번호는 1부터 시작한다.

 

출력

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

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

 

예제

 

풀이 방법

선택한 식재료들의 영양분 합이 최저 영양소 기준을 만족하면서 최소 비용의 식재료의 집합을 찾는 문제였습니다.

 

일단 먼저, 만족하는 집합을 찾기 위해 식재료를 최소 1개 이상 최대 N개 이하를 선택할 수 있기 때문에 반복문을 통해 해당 식재료 개수만큼 선택하여 그 선택된 식재료의 영양분 합이 최저 영양소의 기준을 만족하나 확인해 주었습니다.

isCheck() 메서드에서 선택한 식재료들의 영양분의 합들을 sum배열에 넣어준 뒤, 하나라도 최저 영양소 기준을 만족하지 못한다면 false를 리턴해주고 이외에는 선택된 식재료들의 가격을 비교하여 최소 비용의 식재료의 집합을 찾아주었습니다. 

 

출력 조건이 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력해야 하기 때문에, list에 넣어 정렬을 한 뒤 가장 첫 번째 리스트의 값을 출력해주었습니다. 만약 조건을 만족하는 집합이 없다면 -1을 출력해주었습니다. 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main_BJ_19942_다이어트 {
    
    static int N, M=5,ans =Integer.MAX_VALUE;
    static int [][] nutrients;
    static int [] minN;
    static int []select;
    
    static ArrayList<String> list = new ArrayList<>();
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        nutrients = new int[N][M]; // N개의 영양분을 담을 배열
        minN = new int[4]; // 최저 영양소 기준을 담을 배열
        
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<4;i++) minN[i] = Integer.parseInt(st.nextToken());
        
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++) {
                nutrients[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i=1;i<=N;i++) {
            select = new int[N];
            choice(0,i,0);
        }
        if(list.size()>0) {
            System.out.println(ans);
            Collections.sort(list);
            String st1 = list.get(0);
            for(int i=0;i<st1.length();i++) {
                System.out.print(st1.charAt(i));
            }
        }else System.out.println(-1);
    }
    
    public static void choice(int cnt, int sel, int start) {
        if(cnt==sel) {
           isCheck(sel); //조건체크
            return;
        }
        for(int i=start;i<N;i++) {
                select[cnt]=i;
                choice(cnt+1,sel,i+1);
        }
        
    }
    
    public static boolean isCheck(int sel) {
        int price=0;
        int []sum = new int[4];
        for(int i=0;i<sel;i++) {
                sum[0]+=nutrients[select[i]][0];
                sum[1]+=nutrients[select[i]][1];
                sum[2]+=nutrients[select[i]][2];
                sum[3]+=nutrients[select[i]][3];
                price+=nutrients[select[i]][4];            
        }
        
        for(int i=0;i<4;i++) {
            if(minN[i]>sum[i]) return false;
        }
        
        if(ans>=price) {
            if(ans>price) {
                list.clear();
            }
            String str="";
            for(int i=0;i<sel;i++) {
                str+=(select[i]+1+" ");
            }
            list.add(str);
            ans = price;
        }
        return true;
    }
}