[ 백준/Java ] 19942. 다이어트

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

 

🌱 [ 문제 요약 ]

재료는 단백질, 지방, 탄수화물, 비타민, 가격 상태를 가지고 있다.

영양 성분이 주어질 때, 영양 성분을 만족하면서 가격이 가장 낮은 재료 조합을 구하고

첫째줄에 가격, 두번째줄에 해당 재료의 번호들을 오름차순 출력하라.

( 같은 비용의 집합이 하나 이상이면 사전순으로 빠른 것 / 조건 만족x 인 경우  -1만 출력 / 재료 크기 <= 15 )

 

🌱 [ 알고리즘 선택 ]

가장 낮은 가격을 구해야 하기 때문에 브루트 포스

브루트 포스 방법 : DP / DFS

DP : 영양성분이 4개기 때문에 열을 어떻게 표현 해야할지 어려워서 패스

DFS : 재료 <= 15 이기 때문에 선택 하는 경우, 하지 않는 경우로 표현 가능 ( 2의 15승 )

 

🔥 [ 주의: 사전순 출력 ]

 

DFS는 순서대로 실행 되기 때문에 따로 정렬을 할 필요는 없다.

하지만 재료를 선택 하지 않는 경우를 먼저 실행 하면 밑의 예시를 통과 하지 못한다.

재료를 선택 하는 경우부터 처리 해야 한다.

🌱 [ 전체 코드 ]

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

public class ReSolvedDiet19942 {
    static int minPrice = Integer.MAX_VALUE;
    static List<Ingredient> inputIngredientList;
    static List<Integer> memoryIngredientNumberList;
    static StringBuilder resultSb;

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

        int[] targetInput = Stream.of(br.readLine().split(" "))
        .mapToInt(Integer::parseInt).toArray();
        Ingredient target = createIngredientWithoutPrice(targetInput);
        inputIngredientList = new ArrayList<>();
        memoryIngredientNumberList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            int[] input = Stream.of(br.readLine().split(" "))
            .mapToInt(Integer::parseInt).toArray();
            Ingredient ingredient = createIngredient(input);
            inputIngredientList.add(ingredient);
        }

        dfs(target, createIngredient(allZeroInput()), N, 1);
        if(minPrice == Integer.MAX_VALUE){
            System.out.print("-1");
        }
        else {
            System.out.println(minPrice);
            System.out.print(resultSb);
        }
    }

    private static void dfs(Ingredient target, Ingredient prior, int N, int depth) {
        // 갱신 조건
        if(isSatisfied(target,prior)){
            if(minPrice > prior.price) {
                minPrice = prior.price;
                resultSb = new StringBuilder();
                copyIngredient(resultSb);
            }
        }

        // 탈출 조건
        if(depth == N + 1){
            return;
        }

        Ingredient present = inputIngredientList.get(depth - 1);
        Ingredient next = Ingredient.createEachSumIngredient(prior, present);

        // 선택한 경우
        memoryIngredientNumberList.add(depth);
        dfs(target, next, N, depth + 1);
        memoryIngredientNumberList.remove(Integer.valueOf(depth));

        // 선택x
        dfs(target, prior, N, depth + 1);

    }

    static class Ingredient {
        private int protein;
        private int fat;
        private int carbohydrate;
        private int vitamins;
        private int price;

        public Ingredient(int protein, int fat,
        int carbohydrate, int vitamins, int price) {
            this.protein = protein;
            this.fat = fat;
            this.carbohydrate = carbohydrate;
            this.vitamins = vitamins;
            this.price = price;
        }

        public Ingredient(int protein, int fat, int carbohydrate, int vitamins) {
            this.protein = protein;
            this.fat = fat;
            this.carbohydrate = carbohydrate;
            this.vitamins = vitamins;
        }

        static Ingredient createEachSumIngredient(Ingredient first,Ingredient second){
            int nextProtein = first.protein + second.protein;
            int nextFat = first.fat + second.fat;
            int nextCarbohydrate = first.carbohydrate + second.carbohydrate;
            int nextVitamins = first.vitamins + second.vitamins;
            int nextPrice = first.price + second.price;
            return new Ingredient(nextProtein, nextFat, nextCarbohydrate,
            		   nextVitamins, nextPrice);
        }
    }

    private static int[] allZeroInput() {
        return new int[]{0, 0, 0, 0, 0};
    }

    private static Ingredient createIngredient(int[] input) {
        return new Ingredient(input[0], input[1], input[2], input[3], input[4]);
    }

    private static Ingredient createIngredientWithoutPrice(int[] input) {
        return new Ingredient(input[0], input[1], input[2], input[3]);
    }

    private static boolean isSatisfied(Ingredient target, Ingredient present){
        return target.protein <= present.protein && target.fat <= present.fat
                && target.carbohydrate <= present.carbohydrate
                && target.vitamins <= present.vitamins;
    }

    private static void copyIngredient(StringBuilder resultSb) {
        for(int number : memoryIngredientNumberList){
            resultSb.append(number).append(" ");
        }
    }
}