요리사

문제

문제 설명

두 명의 손님에게 음식을 제공하려고 한다. 두 명의 손님은 식성이 비슷하기 때문에, 최대한 비슷한 맛의 음식을 만들어 내야 한다. N개의 식재료가 있다. 식재료들을 각각 N / 2개씩 나누어 두 개의 요리를 하려고 한다. (N은 짝수이다.) 이때, 각각의 음식을 A음식, B음식이라고 하자. 비슷한 맛의 음식을 만들기 위해서는 A음식과 B음식의 맛의 차이가 최소가 되도록 재료를 배분해야 한다. 음식의 맛은 음식을 구성하는 식재료들의 조합에 따라 다르게 된다. 식재료 i는 식재료 j와 같이 요리하게 되면 궁합이 잘 맞아 시너지 Sij가 발생한다. (1 ≤ i ≤ N, 1 ≤ j ≤ N, i ≠ j) 각 음식의 맛은 음식을 구성하는 식재료들로부터 발생하는 시너지 Sij들의 합이다.

식재료 i를 식재료 j와 같이 요리하게 되면 발생하는 시너지 Sij의 정보가 주어지고, 가지고 있는 식재료를 이용해 A음식과 B음식을 만들 때, 두 음식 간의 맛의 차이가 최소가 되는 경우를 찾고 그 최솟값을 정답으로 출력하는 프로그램을 작성하라.

[예시]

N = 4인 예를 생각해보자. 시너지 Sij는 [Table 1]과 같이 주어진다.

(세로축으로 i번째 위치에 있고 가로축으로 j번째 위치에 있는 값이 Sij이다.)

 [Table 1]

식재료 1과 식재료 2를 A음식으로 만들고 식재료 3과 식재료 4를 B음식으로 만드는 경우를 생각하자.

1) 식재료 1을 식재료 2와 같이 요리했을 때 발생하는 시너지 S12는 5이다.

2) 식재료 2를 식재료 1과 같이 요리했을 때 발생하는 시너지 S21는 4이다.

3) A음식의 맛은 5 + 4 = 9가 된다.

4) 식재료 3을 식재료 4와 같이 요리했을 때 발생하는 시너지 S34는 3이다.

5) 식재료 4를 식재료 3과 같이 요리했을 때 발생하는 시너지 S43은 3이다.

6) B음식의 맛은 3 + 3 = 6이 된다.

따라서, 두 음식 간의 맛의 차이는 |9 – 6| = 3이 된다.

식재료 2와 식재료 4를 A음식으로 만들고 식재료 1과 식재료 3을 B음식으로 만드는 경우를 생각하자.

7) 식재료 2를 식재료 4와 같이 요리했을 때 발생하는 시너지 S24는 1이다.

8) 식재료 4를 식재료 2와 같이 요리했을 때 발생하는 시너지 S42는 2이다.

9) A음식의 전력은 1 + 2 = 3이 된다.

10) 식재료 1을 식재료 3과 같이 요리했을 때 발생하는 시너지 S13은 3이다.

11) 식재료 3과 식재료 1을 같이 요리했을 때 발생하는 시너지 S31은 2이다.

12) B음식의 맛은 3 + 2 = 5가 된다.

따라서, 두 음식간의 맛의 차이는 |3 – 5| = 2가 된다.

이 경우가 A음식과 B음식 간의 맛의 차이가 최소인 경우이다.

다른 경우에서는 맛의 차이가 2보다 작을 수 없다.

따라서, 본 예의 정답은 2가 된다.

제한 사항

입출력 예

입력	출력
3
4
0 5 3 8
4 0 4 1
2 5 0 3
7 2 3 0
4
0 7 1 1
7 0 6 2
1 1 0 2
10 1 9 0
6
0 37 26 52 77 20
32 0 15 26 75 16
54 33 0 79 37 90
92 10 66 0 92 3	#1 2
64 7 89 89 0 21	#2 1
80 49 94 68 5 0	#3 38

제출 코드

import java.io.*;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

/*
 @author ranuinclulus
 @since 2024.08.19
 @link
 @timecomplex
 @performance 
 @category
 @note
 */
public class Solution {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int testNum;
    static int n;
    static boolean[] isSelected;
    static int[][] foonds;
    static int[] plateOne;
    static int[] plateTwo;
    static int min;
    public void solution() throws IOException {
        testNum = Integer.parseInt(br.readLine());
        for (int test = 1; test <= testNum; test++) {
            // 입력
            min = Integer.MAX_VALUE;
            n = Integer.parseInt(br.readLine());
            plateOne = new int[n /2];
            plateTwo = new int[n /2];
            isSelected = new boolean[n];
            foonds = new int[n][n];
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    foonds[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            recursive(0, 0);

            sb.append("#").append(test).append(" ").append(min).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }

    private void recursive(int depth, int start) {
        if (depth == n / 2) {
            int index = 0;
            for (int i = 0; i < n; i++) {
                if (!isSelected[i]) {
                    plateTwo[index] = i;
                    index++;
                }
            }
            calculate();
            return;
        }
        if (start >= n) return;

        isSelected[start] = true;
        plateOne[depth] = start;
        recursive(depth + 1, start + 1);
        isSelected[start] = false;
        recursive(depth, start + 1);
    }

    private void calculate() {
        int sumOne = 0;
        for (int i = 0; i < n / 2; i++) {
            for (int j = i + 1; j < n / 2; j++) {
                sumOne += foonds[plateOne[i]][plateOne[j]];
                sumOne += foonds[plateOne[j]][plateOne[i]];
            }
        }

        int sumTwo = 0;
        for (int i = 0; i < n / 2; i++) {
            for (int j = i + 1; j < n / 2; j++) {
                sumTwo += foonds[plateTwo[i]][plateTwo[j]];
                sumTwo += foonds[plateTwo[j]][plateTwo[i]];
            }
        }

        min = Math.min(min, Math.abs(sumOne - sumTwo));
    }

    public static void main(String[] args) throws IOException {
        new Solution().solution();
    }
}

코드 설명

변수 설명

• int[][] foonds : 재료끼리의 시너지 정보
• int[] plateOne : 첫 번째 요리의 재료
• int[] plateTwo : 두 번째 요리의 재료
• boolean[] isSelected : 첫 번째 요리의 재료로 뽑혔는지 아닌지를 관리하는 배열
• int min : 최대 시너지와 최소 시너지의 차이 최솟값

단계 1: 조합 생성

• plateOne 에 대해 n/2 개의 재료를 뽑아 plateOne 이 만들어질 수 있는 조합을 만듦
• 재료 중 반절을 선택했다면 재귀 종료
• isSelected 에 체크된 재료는 plateOne 에 들어간 재료이기에, isSelected 에 체크되지 않았으면 plateTwo의 재료로 넣어 줌

  private void recursive(int depth, int start) {
          if (depth == n / 2) {
              int index = 0;
              for (int i = 0; i < n; i++) {
                  if (!isSelected[i]) {
                      plateTwo[index] = i;
                      index++;
                  }
              }
              calculate();
              return;
          }
          if (start >= n) return;
  
          isSelected[start] = true;
          plateOne[depth] = start;
          recursive(depth + 1, start + 1);
          isSelected[start] = false;
          recursive(depth, start + 1);
      }

단계 2: 조합에 대한 결과 계산

• sumOne 에 plateOne 요리가 가진 재료들의 시너지들에 대한 값들을 저장
• sumTwo 에 plateTwo 요리가 가진 재료들의 시너지들에 대한 값들을 저장
• 차이를 구한 뒤 절댓값을 취해 min 갱신

   private void calculate() {
          int sumOne = 0;
          for (int i = 0; i < n / 2; i++) {
              for (int j = i + 1; j < n / 2; j++) {
                  sumOne += foonds[plateOne[i]][plateOne[j]];
                  sumOne += foonds[plateOne[j]][plateOne[i]];
              }
          }
  
          int sumTwo = 0;
          for (int i = 0; i < n / 2; i++) {
              for (int j = i + 1; j < n / 2; j++) {
                  sumTwo += foonds[plateTwo[i]][plateTwo[j]];
                  sumTwo += foonds[plateTwo[j]][plateTwo[i]];
              }
          }
  
          min = Math.min(min, Math.abs(sumOne - sumTwo));
      }