[SWEA] #4012 - 요리사

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH 

SW Expert Academy

 

💡 문제

---

[설명]

두 명의 손님에게 음식을 제공하려고 한다.

두 명의 손님은 식성이 비슷하기 때문에, 최대한 비슷한 맛의 음식을 만들어 내야 한다.

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개에서 N/2개의 조합을 찾는데 조합에 사용된 식재료는 방문했다고 표시한다.

그러면 남은 N/2개는 방문하지 않았으므로 자연스럽게 어떤 것이 남았는지 알 수 있다.

이를 이용해 각 식재료로 만든 음식의 시너지를 구할 수 있고, 이 시너지의 차이를 구하면 문제를 해결할 수 있다.

조합에 따라 시너지가 다르기 때문에 모든 조합의 시너지를 구한 뒤에 최소 시너지의 차이를 구해야 한다.

 

💡 소스코드

---

package SWEA;

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

public class SWEA_P4012_요리사 {
	static int N;
	static int[][] map;
	static boolean[] visited;
	static int MIN;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P4012_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sz;
		int T = Integer.parseInt(br.readLine());

		for (int TC = 1; TC <= T; TC++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N + 1][N + 1];
			visited = new boolean[N + 1];
			MIN = Integer.MAX_VALUE;

			for (int i = 1; i <= N; i++) {
				sz = new StringTokenizer(br.readLine());
				for (int j = 1; j <= N; j++) {
					map[i][j] = Integer.parseInt(sz.nextToken());
				}
			}

			combination(1, 0);
			System.out.println("#" + TC + " " + MIN);
		}
		br.close();
	}

	public static void combination(int start, int len) {
		if (len == N / 2) {
			solve();
			return;
		}

		for (int i = start; i <= N; i++) {
			visited[i] = true;
			combination(i + 1, len + 1);
			visited[i] = false;
		}
	}

	public static void solve() {
		int x = 0, y = 0, result = 0;

		for (int i = 1; i < N; i++) {
			for (int j = i + 1; j <= N; j++) {
				if (visited[i] && visited[j]) {
					x += map[i][j] + map[j][i];
				} 
				
				else if (!visited[i] && !visited[j]) {
					y += map[i][j] + map[j][i];
				}
			}
		}
		
		result = Math.abs(x - y);
		if (result < MIN)
			MIN = result;
	}

}

 

💡 결과

---