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

문제 설명

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

 

▸ 문제

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

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

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

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

 

▸ 입력

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

 

▸ 출력

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

 

📍 문제 정보

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

 

문제 풀이

이 문제는 부분집합(Subset)을 통해 가능한 모든 재료 조합을 만들 수 있으며, 백트래킹을 사용해 모든 재료의 부분집합을 탐색하여 해결했다.

 

각 부분집합은 선택된 재료 조합을 의미하며, 선택된 재료들의 신맛은 곱, 쓴맛은 합으로 계산한다.

모든 부분 집합을 확인하면서 아무 재료도 선택하지 않은 경우는 제외하고, 각 조합의 신맛과 쓴맛의 차이(Math.abs(mulSour-sumBitter)) 중 가장 작은 값을 구해 출력한다.

 

코드

메모리 : 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);
    }
}

부분집합(Subset)에 대한 자세한 설명이 궁금하다면 링크 클릭!

백트래킹(BackTracking)에 대한 자세한 설명이 궁금하다면 링크 클릭!