2961도영이가 만든 맛있는 음식

LJM·2023년 1월 13일
0

백준풀기

목록 보기
31/259

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


첫번시도에서 통과 했는데 코드 정리하다보니 최적화를 더 할 수 있을거 같아서 두번째 시도에서 시간을 많이 단축하였다. 완전탐색에서 중복재료선택을 줄였다.

재료가 3개면, 완전탐색을 통해 3개중 1개만 사용하는 경우, 2개 사용하는 경우, 3개 사용하는 경우를 다 구해주고 케이스마다 신맛 단맛의 차이를 계산해서 풀었다

예를 들어 재료가 1,2,3 이라고 해보자 그러면
1
2
3
1,2
1,3
2,3
1,2,3

7가지 테스트케이스가 나온다.

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

public class Main {

    static class Ingredient
    {
        int ingID;//재료의 고유번호. 최적화 위해 필요.
        int bitter;//쓴맛
        int sour;//신맛

        public Ingredient(int sour, int bitter, int ingID) {
            this.sour = sour;
            this.bitter = bitter;
            this.ingID = ingID;
        }
    }

    static int IngredientCnt;
    static ArrayList<Ingredient> list = new ArrayList<>();
    static boolean[] checked = new boolean[10];
    static Ingredient[] food = new Ingredient[10];

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        IngredientCnt = Integer.parseInt(br.readLine());

        String[] input;
        for(int i =0; i < IngredientCnt; ++i)
        {
            input = br.readLine().split(" ");
            list.add(new Ingredient(Integer.parseInt(input[0]), Integer.parseInt(input[1]), i));
        }


        int answer = Integer.MAX_VALUE;
        for(int i = 1; i < IngredientCnt+1; ++i)
        {
            clearFood(i);
            answer = Math.min(answer, search(0, i));
        }

        System.out.println(answer);

    }

    static void clearFood(int targetlevel)//초기화하지 않으면 탐색이 비정상적으로 진행됨
    {
        for(int i = 0; i < targetlevel; ++i)
        {
            food[i] = null;
        }
        food[0] = list.get(0);//search 함수 for문 일단 시작하기위해 세팅
    }

    static int search(int level, int targetlevel)
    {
        if(level == targetlevel)
        {
            int sour = 1;
            int bitter = 0;

            for(int i =0; i < level; ++i)
            {
                sour *= food[i].sour;
                bitter += food[i].bitter;
            }

            return Math.abs(sour-bitter);
        }

        int diff = Integer.MAX_VALUE;
        //이전에 테스트케이스에 선택된 재료 제외하기위해. food에서 사용된것보다 높은 id의 재료사용 예) 123, 132 는 중복이다
        for(int i = food[level==0? level:level-1].ingID; i < IngredientCnt; ++i)
        {
            if(checked[i] == false)
            {
                checked[i] = true;
                food[level] = list.get(i);
                diff = Math.min(diff, search(level+1, targetlevel));
                checked[i] = false;
            }
        }

        return diff;
    }
}
profile
게임개발자 백엔드개발자

0개의 댓글