문제링크

풀이1

DFS를 사용한 브루트포스

최소한 하나 이상의 재료를 선택해서,
|신맛 - 쓴맛|의 최솟값을 구해야 한다.
재료 목록을 ArrayList에 저장한다.

• DFS(깊이 우선 탐색)으로 각 재료를 선택하거나, 선택하지 않거나의 두 경우로 나누어 진행한다.
  → 총 $2^n$가지의 조합을 탐색하게 된다.

• 이때, 재료를 하나도 선택하지 않은 경우(공집합)는 무시해야 하므로,
  이를 방지하기 위해 used라는 boolean 플래그를 사용한다.

  • 재료를 선택할 경우 → used = true로 설정해서 다음 재귀에 전달
  • 선택하지 않을 경우 → 기존 used 값을 그대로 유지

• 모든 재귀 호출이 끝날 때, used == true인 경우에만
  |신맛 - 쓴맛|을 계산하고, 최소값을 갱신한다.

코드1

package BOJ;

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

public class sol2961 {
    static int n;
    static long min = Long.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        ArrayList<Material> materials = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            materials.add(new Material(s, b));
        }
        dfs(materials, 0, 1L, 0L, false);	//	신 맛은 곱이기 때문에 초기 값을 1로 설정
        System.out.println(min);
    }

    public static void dfs(ArrayList<Material> materials, int idx, long sumS, long sumB, boolean used) {
        if (used) {
            long currVal = Math.abs(sumS - sumB);
            min = Math.min(currVal, min);
        }

        if (idx == n) {
            return;
        }
        dfs(materials, idx + 1, materials.get(idx).s * sumS, materials.get(idx).b + sumB, true);
        dfs(materials, idx + 1,  sumS, sumB, used);
    }

    public static class Material {
        long s, b;

        Material(long s, long b) {
            this.s = s;
            this.b = b;
        }
    }
}

풀이2

비트마스킹을 사용한 브루트포스 코드이다.

• 모든 재료의 선택/비선택 조합을 탐색하기 위해 비트마스킹을 사용한다.

• n개의 재료가 있을 때, 가능한 조합은 $2^n$개 → 0부터 (1 << n) - 1까지의 수로 표현 가능

  • 재료의 사용 여부를 비트로 표현한다.
    예를 들어 재료가 {a, b, c, d} 4개 이면, 0001이라면 d만 사용, 0011이면 c, d를 사용하는 것이다.

• 이 중 0 (즉, 아무 재료도 선택하지 않은 경우)는 문제 조건에 위배되므로 제외하고
  → 1부터 (1 << n) - 1까지 반복

1. i = 1부터 i < (1 << n)까지 반복하며 모든 조합을 탐색
2. 각 i에 대해:
   • 신맛(sour)을 1로 초기화 (곱셈이므로)
   • 쓴맛(bitter)을 0으로 초기화 (덧셈이므로)
3. j = 0부터 n - 1까지 순회하면서:
   • i의 j번째 비트가 1이면 → j번째 재료를 선택한 것

코드2

package BOJ;

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

public class sol2961_2 {
    static int n;
    static long min = Long.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        ArrayList<Material> materials = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            materials.add(new Material(s, b));
        }
        int mask = 1 << n;
        for (int i = 1; i < mask; i++) {
            long sour = 1;
            long bitter = 0;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {  //  j번째 비트가 켜져있으면
                    sour *= materials.get(j).s;
                    bitter += materials.get(j).b;
                }
            }
            long val = Math.abs(sour - bitter);
            min = Math.min(val, min);
        }
        System.out.println(min);
    }

    public static class Material {
        long s, b;

        Material(long s, long b) {
            this.s = s;
            this.b = b;
        }
    }
}