[BOJ] 2961 도영이가 만든 맛있는 음식 - JAVA

1. 문제

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

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

---

2. 풀이

모든 경우의 수를 체크하되, 각각의 자리수가 1인지 아닌지 체크해서(비트마스크) 1이면 그 재료를 넣었다는 뜻이다. 두 번 풀어서 두 가지 버전의 풀이가 있다.

 

부분집합 메서드 이용

메인

1.  재료를 입력받는다.

2.  재료 고르는 메서드를 호출한다.

3.  답을 출력한다.

static int N;
static int[][] ingredient;
static int MIN = 1_000_000_000;
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   N = Integer.parseInt(in.readLine());
   ingredient = new int[N][2];
   StringTokenizer st;
   for(int i=0;i<N;i++){
      st = new StringTokenizer(in.readLine());
      ingredient[i][0] = Integer.parseInt(st.nextToken());
      ingredient[i][1] = Integer.parseInt(st.nextToken());
   }

   choose(0,0);
   System.out.println(MIN);
}

 

재료 고르기

비트마스킹을 응용한 부분집합 메서드다. idx==N이고 choice>0일 때 MIN값과 cook메서드 반환값을 비교하고 갱신한다.

public static void choose(int choice, int idx){
   if(idx==N){
      if(choice == 0) return;
      MIN = Math.min(MIN, cook(choice));
      return;
   }

   choose(choice, idx+1);
   choose(choice|1<<idx, idx+1);
}

 

신맛, 쓴맛 차이 구하기

1.  비트마스킹 된 숫자를 받아서 &연산을 이용해 그 재료를 뽑았는지 확인한다.

2.  뽑았다면 신맛에 곱하고 쓴맛엔 더한다.

3.  마지막에 그 차이를 출력한다.

public static int cook(int choice){
   int sour = 1;
   int bitter = 0;

   for(int i=0;i<N;i++){
      if((choice&(1<<i)) == 0) continue;
      sour *= ingredient[i][0];
      bitter += ingredient[i][1];
   }

   return Math.abs(sour-bitter);
}

 

전체 코드

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

public class BOJ_2961_도영이가만든맛있는음식 {
   static int N;
   static int[][] ingredient;
   static int MIN = 1_000_000_000;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(in.readLine());
      ingredient = new int[N][2];
      StringTokenizer st;
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         ingredient[i][0] = Integer.parseInt(st.nextToken());
         ingredient[i][1] = Integer.parseInt(st.nextToken());
      }

      choose(0,0);
      System.out.println(MIN);
   }

   public static void choose(int choice, int idx){
      if(idx==N){
         if(choice == 0) return;
         MIN = Math.min(MIN, cook(choice));
         return;
      }

      choose(choice, idx+1);
      choose(choice|1<<idx, idx+1);
   }

   public static int cook(int choice){
      int sour = 1;
      int bitter = 0;

      for(int i=0;i<N;i++){
         if((choice&(1<<i)) == 0) continue;
         sour *= ingredient[i][0];
         bitter += ingredient[i][1];
      }

      return Math.abs(sour-bitter);
   }
}

 

반복문 이용

2^N은 N으로 만들 수 있는 모든 경우의 수(공집합 뺌)를 구할 수 있다. 따라서 1부터 2^N까지 탐색하면서 쓴맛, 신맛의 차이를 구한다.

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

public class BOJ_2961_도영이가만든맛있는음식 {

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(in.readLine());
        int[][] items = new int[N][2];//0 신맛 1 쓴맛
        int diff = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(in.readLine());
            items[i][0] = Integer.parseInt(st.nextToken());
            items[i][1] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i < 1 << N; i++) {//2^N--> 모든 경우의 수
            int S = 1, B = 0;
            for (int j = 0; j < N; j++) { // 0001 0010 0100 1000
                if ((i & 1 << j) != 0) {
                    S *= items[j][0];
                    B += items[j][1];
                }
            }
            diff = Math.min(diff, Math.abs(S - B));
        }

        System.out.println(diff);

    }

}

---

3. 결과

1년 전에는 반복문으로 풀었고, 오늘은 부분집합 메서드를 이용해서 풀었다.