4012. [모의 SW 역량테스트] 요리사

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

SW Expert Academy

 

문제 해석

두 명의 손님에게 음식을 제공
두 손님은 식성이 비슷해서, 최대한 비슷한 맛의 음식으로 제공하고자 함
N개의 식재료가 존재
식재료를 각각 N/2 씩 나누어 요리하려고 함 (N = 짝수)
음식의 맛은 음식을 구성하는 식재료의 조합에 따라 달라짐

 

조합이라는 시너지가 존재하며 시너지 배열을 통해 계산하여 이 시너지가 최소가 되도록 구현해야 한다.

 

예를 들어 음식 A를 위해 식재료 2, 3, 6이 사용되었다면 A의 맛은 S [2][3] + S [3][2] + S [3][6] + S [6][3] + S [2][6] + S [6][2]입니다.

 

 

문제 풀이 전 설계

식재료는 최대 16개이기 때문에 16C8을 해도 시간 복잡도가 괜찮을 것 같아 조합으로 풀려고 했습니다.

또한 조합을 한번 한 뒤에도 다시 N/2개 중 2개를 뽑아 시너지를 계산해야 합니다.

 

 

문제 풀이하면서 생각한 점

(N) C (N/2)를 활용해서 우선 절반씩 나누어 주었습니다.

그렇게 되면 N/2개씩 뽑힌 combinatedArray가 쭉 나오는데 이때 combinatedArray의 절반만 사용하여도 나머지 음식들을 구할 수 있습니다.

 

예를 들자면

i번째 array와    N-1-i번째 array는 같은 원소를 중복해서 가지고 있지 않습니다.
즉 N=6이면 1,2,3 / 4,5,6   또는 1,5,6 / 2,3,4와 같은 구조를 가집니다.

따라서 이를 combinatedResultList라는 리스트에 저장하고 이 리스트의 절반까지 돌아주면서

combinatedResultList.get(i)와 combinatedResultList.get(N-i-1)을 활용하여 음식의 시너지를 계산하여 문제를 해결했습니다.

 

TestCase를 반복할 때마다 combinatedResultList를 초기화시켜주어야 합니다.

 

 

코드

package day0216;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/*
문제 해석
두 명의 손님에게 음식을 제공
두 손님은 식성이 비슷해서, 최대한 비슷한 맛의 음식으로 제공하고자 함
N개의 식재료가 존재
식재료를 각각 N/2 씩 나누어 요리하려고 함 (N = 짝수)
음식의 맛은 음식을 구성하는 식재료의 조합에 따라 달라짐

식재료는 최대 16개
16C8 
 
 */
public class Solution_4012_요리사 {
	static int[][] synergy;
	static int minTasteGap;
	static int[] combinatedArray;
	static List<int[]> combinatedResultList = new ArrayList<int[]>();

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int tc = 1; tc <= T; tc++) {
			// init
			minTasteGap = Integer.MAX_VALUE;

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

			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					synergy[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			combinatedArray = new int[N / 2];
			// N개중에 N/2를 나누어 뽑음
			combination(0, 0, N / 2);

			// 뽑은 결과의 시너지 계산
			int size = combinatedResultList.size();
			for (int i = 0; i < size / 2; i++) {

				// i번째 array와 N-1-i번째 array는 같은원소를 중복해서 가지고 있지 않음
				// 즉 N=6이면 1,2,3 / 4,5,6 또는 1,5,6 / 2,3,4 와 같이 가지고 있음

				// 시너지A 계산
				int synergyA = 0;
				int[] tempA = combinatedResultList.get(i);
				int sizeA = tempA.length;
				for (int j = 0; j < sizeA - 1; j++) {
					for (int k = j + 1; k < sizeA; k++) {
						int tempY = tempA[j] - 1;

						int tempX = tempA[k] - 1;
						synergyA = synergyA + synergy[tempY][tempX] + synergy[tempX][tempY];
					}
				}

				// 시너지B 계산
				int synergyB = 0;
				int[] tempB = combinatedResultList.get(size - i - 1);
				int sizeB = tempB.length;

				for (int j = 0; j < sizeB - 1; j++) {
					for (int k = j + 1; k < sizeB; k++) {
						int tempY = tempB[j] - 1;
						int tempX = tempB[k] - 1;
						synergyB = synergyB + synergy[tempY][tempX] + synergy[tempX][tempY];
					}
				}

				// 시너지 A와 B의 차이 계산해서 최소일경우 minTasteGap값 update
				int synergyGap = Math.abs(synergyA - synergyB);
				minTasteGap = minTasteGap < synergyGap ? minTasteGap : synergyGap;
			}

			sb.append("#" + tc + " " + minTasteGap + "\n");
			combinatedResultList.clear();

		}
		System.out.println(sb);
	}

	private static void combination(int cnt, int start, int finish) {
		if (cnt == finish) {
			int[] clone = combinatedArray.clone();
			combinatedResultList.add(clone);
			return;
		}
		for (int i = start; i < synergy.length; i++) {
			combinatedArray[cnt] = i + 1;
			combination(cnt + 1, i + 1, finish);
		}
	}

}