[백준] 19942 다이어트 - Java

 

 

 

문제 출저

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

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, f, s, v, i와 같이 주어진다. 식재료의 번호는 1부터 시작한다.

 

출력

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

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

제한

•  3≤�≤15$3 \le N \le 15$ 
•  0≤mp,mf,ms,mv≤500
•  mp+mf+ms+mv>0
•  0≤p,f,s,v,c≤500

예제 입력 1 복사

6
100 70 90 10
30 55 10 8 100
60 10 10 2 70
10 80 50 0 50
40 30 30 8 60
60 10 70 2 120
20 70 50 4 4

예제 출력 1 복사

134
2 4 6

 

 

 

 

문제 풀이

백트래킹으로 문제를 풀었습니다. 

 

재료 저장 : class Ingredient 생성, Map<Integer, Ingredien> 

경우의 수 확인 : dfs, 재귀 함수 사용 (이 때 정답은 사전순으로 3 이랑 1,2,3 중 1,2,3이 사전순으로 앞서므로 1,2,3이 정답입니다. 따라서 넣는 것을 재귀 순서 앞에 배치합니다.)

 

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
다이어트
https://www.acmicpc.net/problem/19942

8% 오답
만족하는 조건이 없을 때 -1 출력 처리

반례
3
0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0

사전순으로 앞선 것을 뽑아야 한다.
즉 3이 아니라 1 2 3 을 뽑아야 한다..

 */

public class Main {

    static int n;
    static int[] m;
    static Map<Integer, Ingredient> ingredients;

    static int answer;
    static List<Integer> choose;
    static List<Integer> answerChoose;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

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

        ingredients = new HashMap<>();

        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 cost = Integer.parseInt(st.nextToken());
            ingredients.put(i, new Ingredient(p, f, s, v, cost));
        }

        answer = Integer.MAX_VALUE;
        choose = new ArrayList<>();
        dfs(0, 0, 0, 0, 0, 0);


        if (answer == Integer.MAX_VALUE) {
            System.out.println(-1);
            return;
        }

        System.out.println(answer);
        for (int number : answerChoose) {
            System.out.print(number+1 + " ");
        }


    }

    public static void dfs(int stage, int sumP, int sumF, int sumS, int sumV, int sumCost) {

        if (sumCost > answer) {
            return;
        }

        if(sumP >= m[0] && sumF >= m[1] && sumS >= m[2] && sumV >= m[3]) {
            if (answer > sumCost) {
                answer = sumCost;
                answerChoose = new ArrayList<>();
                answerChoose.addAll(choose);
            }
            return;
        }

        if (stage >= n) {
            return;
        }

        // 선택한 경우
        choose.add(stage);
        Ingredient ingredient = ingredients.get(stage);
        dfs(stage + 1,
                sumP + ingredient.p,
                sumF + ingredient.f,
                sumS + ingredient.s,
                sumV + ingredient.v,
                sumCost + ingredient.cost);
        choose.remove(Integer.valueOf(stage));

        // 선택 안한 경우
        dfs(stage + 1, sumP, sumF, sumS, sumV, sumCost);
    }

    public static class Ingredient {

        int p;
        int f;
        int s;
        int v;
        int cost;

        Ingredient(int p, int f, int s, int v, int cost) {
            this.p = p;
            this.f = f;
            this.s = s;
            this.v = v;
            this.cost = cost;
        }

    }

}