[백준] 2961. 도영이가 만든 맛있는 음식 (부분집합/Java)

[백준] 2961. 도영이가 만든 맛있는 음식

💡 문제 분석

N개의 재료 중 일부를 선택해서 요리를 만들 때, 신맛과 쓴맛의 차이를 최소화하는 문제다.

• 신맛: 선택한 재료들의 신맛을 모두 곱한 값
• 쓴맛: 선택한 재료들의 쓴맛을 모두 더한 값
• 목표: |신맛 - 쓴맛|의 최솟값 구하기

핵심은 부분집합(Subset) 문제라는 것이다. N개 재료 중 적어도 1개 이상을 선택하는 모든 경우를 탐색해야 한다.

 

📌 풀이 과정

풀이 방법 1: 재귀 (백트래킹)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    static int N, answer;
    static int[][] foodItems;

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

       for(int i = 0; i < N; i++){
          StringTokenizer st = new StringTokenizer(br.readLine());
          foodItems[i][0] = Integer.parseInt(st.nextToken()); // 신맛
          foodItems[i][1] = Integer.parseInt(st.nextToken()); // 쓴맛
       }

       answer = Integer.MAX_VALUE;
       cook(0, 1, 0, 0);
       System.out.println(answer);
    }

    private static void cook(int idx, int S, int B, int count){
       // 재료 1개 이상 사용한 경우에만 최소값 갱신
       if(count > 0) {
           answer = Math.min(Math.abs(S - B), answer);
       }
       
       if(idx == N) return;

       // 재료 선택O
       cook(idx + 1, S * foodItems[idx][0], B + foodItems[idx][1], count + 1);
       // 재료 선택X
       cook(idx + 1, S, B, count);
    }
}

재귀 풀이의 특징

• 직관적: 각 재료를 선택하거나 선택하지 않는 두 가지 경우로 나누어 생각
• 매개변수 활용: idx(현재 위치), S(신맛), B(쓴맛), count(선택된 재료 수)
• 백트래킹: 모든 경우를 탐색하되, 조건에 맞는 경우에만 답을 갱신

 

풀이 방법 2: 비트마스킹 (반복문)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    static int N, answer;
    static int[][] foodItems;

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

       for(int i = 0; i < N; i++){
          StringTokenizer st = new StringTokenizer(br.readLine());
          foodItems[i][0] = Integer.parseInt(st.nextToken()); // 신맛
          foodItems[i][1] = Integer.parseInt(st.nextToken()); // 쓴맛
       }

       answer = Integer.MAX_VALUE;

       // 1부터 (1<<N)-1까지 모든 부분집합 탐색
       for(int mask = 1; mask < (1 << N); mask++){
          int S = 1, B = 0;

          for(int i = 0; i < N; i++){
             if((mask & (1 << i)) != 0){
                S *= foodItems[i][0];
                B += foodItems[i][1];
             }
          }

          answer = Math.min(answer, Math.abs(S - B));
       }

       System.out.println(answer);
    }
}

비트마스킹 핵심 개념

비트마스킹은 정수의 각 비트를 사용해서 집합의 원소 포함 여부를 표현하는 방법이다.

1. 전체 경우의 수 계산

for(int mask = 1; mask < (1 << N); mask++)

• (1 << N) = 2^N (N개 재료로 만들 수 있는 모든 경우의 수)
• mask = 1부터 시작하는 이유: 0은 아무 재료도 안 쓰는 경우라서 제외
• 예: N=3이면 1부터 7까지 반복

2. 각 재료 선택 여부 확인

if((mask & (1 << i)) != 0)

• (1 << i): i번째 비트만 1인 수 (예: i=2면 100₂)
• mask & (1 << i): mask의 i번째 비트가 1인지 확인
• 결과가 0이 아니면 i번째 재료를 사용한다는 뜻

3. 구체적인 예시 (N=3인 경우)

mask = 1 (이진수: 001₂) → 재료 0만 선택
mask = 2 (이진수: 010₂) → 재료 1만 선택  
mask = 3 (이진수: 011₂) → 재료 0, 1 선택
mask = 4 (이진수: 100₂) → 재료 2만 선택
mask = 5 (이진수: 101₂) → 재료 0, 2 선택
mask = 6 (이진수: 110₂) → 재료 1, 2 선택
mask = 7 (이진수: 111₂) → 재료 0, 1, 2 모두 선택

mask=5 (101₂)일 때의 동작:

i=0: mask & (1<<0) = 101₂ & 001₂ = 001₂ ≠ 0 → 재료 0 사용
i=1: mask & (1<<1) = 101₂ & 010₂ = 000₂ = 0  → 재료 1 사용 안함  
i=2: mask & (1<<2) = 101₂ & 100₂ = 100₂ ≠ 0 → 재료 2 사용

 

두 풀이 방법 비교

 

구분	재귀 (백트래킹)	비트마스킹
직관성	높다 (선택/비선택이 명확)	중간 (비트 연산 이해 필요)
메모리	재귀 스택 사용	스택 사용 없음
속도	약간 느리다 (함수 호출 오버헤드)	빠르다 (반복문 + 비트 연산)
코드 길이	약간 길다	짧다
확장성	조건 추가하기 쉽다	비트 연산 범위 제한

 

🤔 언제 어떤 방법을 사용할까?

재귀 방법이 좋은 경우

• 복잡한 조건이나 가지치기가 필요한 경우
• 코드의 직관성이 중요한 경우
• 부분집합 외에 다른 탐색 로직이 필요한 경우

비트마스킹이 좋은 경우

• 단순한 부분집합 문제
• 성능이 중요한 경우
• N이 작은 경우 (보통 N ≤ 20)

두 방법은 시간복잡도가 O(2^N)으로 동일하다. 비트마스킹은 부분집합 문제에서 매우 유용한 테크닉이라고 한다!!