[SWEA] 4012번 - 요리사 풀이 및 코드 분석 (Java)

문제 링크

---

1. 문제 분석

📌 문제 개요

• N개의 재료를 N/2개씩 두 그룹으로 나누어 요리를 만든다.
• 두 요리의 맛의 차이가 최소가 되도록 재료를 배분해야 한다.
• 각 재료 i와 j가 함께 사용되면 시너지(Sij)가 발생한다.
• 두 요리의 맛 차이 |A - B| 를 최소화하는 경우를 찾는다.

🎯 요구사항

1. N개의 재료를 두 개의 요리에 N/2개씩 배분해야 한다.
2. 각 요리의 맛을 계산하여 두 음식의 맛 차이가 최소가 되도록 한다.
3. 완전 탐색(백트래킹)으로 모든 경우를 조사해야 한다.

---

2. 해결 방법

🔹 핵심 개념

• 조합(combination) 을 이용하여 N/2개의 재료를 선택하여 요리 A를 만든다.
• 선택되지 않은 재료들로 요리 B를 만든다.
• 각 요리의 맛을 계산하여 차이를 최소화한다.
• 백트래킹을 활용하여 최적의 조합을 찾는다.

🔑 해결 절차

1. 모든 가능한 재료 조합을 완전 탐색
   • comb()을 이용하여 N개의 재료 중 N/2개를 선택
   • 선택된 A를 제외한 나머지 재료는 B 그룹이 된다.
2. 각 요리의 맛을 계산
   • calFood()에서 sumA와 sumB를 계산
   • Sij와 Sji를 합산하여 시너지를 계산
3. 맛 차이가 최소가 되는 경우를 갱신
   • answer = min(answer, |sumA - sumB|)

---

3. 코드 구현

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

public class Solution {
    static int N, answer;
    static ArrayList<Integer> A;
    static int[][] S;

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

        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            sb.append("#").append(t).append(" ");
            answer = Integer.MAX_VALUE;

            N = Integer.parseInt(br.readLine());
            S = new int[N][N];

            for (int r = 0; r < N; r++) {
                st = new StringTokenizer(br.readLine());
                for (int c = 0; c < N; c++) {
                    S[r][c] = Integer.parseInt(st.nextToken());
                }
            }

            A = new ArrayList<>();
            comb(0);

            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }

    // 백트래킹을 이용한 조합 탐색
    private static void comb(int d) {
        if (A.size() == N / 2) {
            calFood();
            return;
        }

        for (int i = d; i < N; i++) {
            A.add(i);
            comb(i + 1);
            A.remove(A.size() - 1);
        }
    }

    // A 요리를 선택한 후, B 요리를 만들어 맛 차이 계산
    private static void calFood() {
        ArrayList<Integer> B = new ArrayList<>();
        int sumA = 0, sumB = 0;

        for (int i = 0; i < N; i++) {
            if (!A.contains(i)) {
                B.add(i);
            }
        }

        // A 요리의 시너지 계산
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j < A.size(); j++) {
                sumA += S[A.get(i)][A.get(j)];
            }
        }

        // B 요리의 시너지 계산
        for (int i = 0; i < B.size(); i++) {
            for (int j = 0; j < B.size(); j++) {
                sumB += S[B.get(i)][B.get(j)];
            }
        }

        answer = Math.min(answer, Math.abs(sumA - sumB));
    }
}

---

4. 코드 분석

🔹 주요 알고리즘

1. 백트래킹을 활용한 조합 탐색
   • N개의 재료 중 N/2개를 선택하는 모든 조합을 생성
   • 이미 선택된 경우 탐색을 중단하여 중복 계산을 방지
2. 두 음식의 맛 계산
   • Sij와 Sji를 합산하여 각 음식의 총 시너지 값을 계산
   • 두 음식의 맛 차이를 계산하여 최소값을 갱신

🔹 시간 복잡도 분석

• 조합 생성: O(2^N)
• 각 조합에서 시너지 계산: O(N^2)
• 최악의 경우 (N=16)
  • O(2^16 * 16^2) = O(65536 * 256) ≈ O(1.6 * 10^7)
  • 백트래킹을 활용하면 충분히 해결 가능

---

5. 개선할 점 및 대체 방법

✅ 개선할 점

1. 비트마스킹을 활용한 조합 최적화
   • N이 작으므로 비트마스크를 활용하면 탐색 속도를 개선 가능
   • 1 << N을 활용하여 모든 조합을 빠르게 탐색 가능
2. DP를 활용한 부분 문제 최적화
   • dp[A]를 저장하면 중복 계산을 줄일 수 있음

🔄 대체 방법

1. Bitmask DP 적용 가능
   • N이 작으므로 bitmask를 이용하면 탐색 속도 개선 가능
2. DFS 활용 가능
   • DFS를 사용하여 N/2개의 조합을 선택하는 방식도 가능