[Boj_2961] 도영이가 만든 맛있는 음식

📎 문제 링크

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

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

 

▸ 문제

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

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

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

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

 

▸ 입력

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

 

▸ 출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다.

 

📍 문제 정보

• 🥈 문제 레벨 : 실버 2
• 🔔  문제 유형 : 브루트포스 알고리즘, 비트마스킹, 백트래킹
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

• 백트래킹을 이용한 부분집합으로 문제를 해결했다.
• 모든 재료의 부분집합을 구한 뒤, 재료를 하나도 사용하지 않았을 때를 제외한 신맛의 곱과 쓴맛의 합의 차이 중 가장 작은 값을 출력한다.

 

🔍 부분집합이란(Subset) ?

• 한 집합의 원소들로만 구성한 집합을 말한다.
  • 집합의 원소가 총 n개일 때, 공집합을 포함한 부분집합의 개수는 2^n개다.
  • 즉, 각각의 원소들을 부분집합에 포함시키거나 포함하지 않는 두 가지 경우를 모든 원소에 적용한 것의 경우의 수와 같다.
• 재귀를 이용하여 부분집합을 구현할 때는
• 아래와 같은 두 가지 경우에 대해 모두 확인한 후 현재 인덱스가 n이 되었을 때 출력한다.
  • 현재 인덱스를 포함하는 경우
  • 현재 인덱스를 포함하지 않는 경우

 

✔ 최종 코드

메모리 : 11632 KB
시간 : 76 ms

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

public class Main {
    static int n ;
    static int[][] taste;
    static boolean[] checked;
    static int ans = Integer.MAX_VALUE; // 신맛과 쓴맛의 최솟값
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine()); // 재료의 개수

        taste = new int[n][2]; // 신맛과 쓴맛을 저장 할 배열
        checked = new boolean[n]; // 사용한 신맛과 쓴맛을 체크 할 방문배열
        // 신맛 쓴맛 입력
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            taste[i][0] = Integer.parseInt(st.nextToken());
            taste[i][1] = Integer.parseInt(st.nextToken());
        }
        // 인덱스, 사용한 재료의 개수, 신맛(*), 쓴맛(+)
        dfs(0, 0, 1, 0);
        bw.append(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int idx, int material, int mulSour, int sumBitter) {
        if (idx == n) { // 부분집합을 완성했다면
            if (material != 0) { // 재료는 적어도 하나 사용해야 함
                ans = Math.min(ans, Math.abs(mulSour-sumBitter));
            }
            return;
        }
        
        // 부분집합 만들기
        // 현재 인덱스 포함
        checked[idx] = true;
        dfs(idx+1, material+1, mulSour*taste[idx][0], sumBitter+taste[idx][1]);
        // 현재 인덱스 포함 안함
        checked[idx] = false;
        dfs(idx+1, material, mulSour, sumBitter);
    }
}

 

 

📍 함께 풀어보면 좋은 백준 문제

• 15661 링크와 스타트