[모의 SW 역량테스트] 요리사 -Java

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH&categoryId=AWIeUtVakTMDFAVH&categoryType=CODE

SW Expert Academy

package SW_Expert_Academy;

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

public class 요리사 {
	static int min, foodInfo[][], N;
	static boolean check[];

	public static void main(String[] args) throws NumberFormatException, IOException {

		StringTokenizer st = null;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			
			N=Integer.parseInt(br.readLine());
			
			foodInfo=new int[N][N];
			check=new boolean[N];
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					foodInfo[i][j]=Integer.parseInt(st.nextToken());
				}
			}
			min=Integer.MAX_VALUE;
			combination(0,0,N/2);
			System.out.println("#"+tc+" "+min);
		}

	}


	private static void combination(int cnt, int start, int end) {
		if(cnt==end) {
			int synergy=0;
			List<Integer> foodA=new ArrayList<>();
			List<Integer> foodB=new ArrayList<>();
			for(int i=0; i<N; i++) {
				if(check[i]) foodA.add(i);
				else foodB.add(i);
			}
			
			min=Math.min(min, Math.abs(cal(foodA)-cal(foodB)));
			return;
		}
		
		for(int i=start; i<N; i++) {
			check[i]=true;
			combination(cnt+1, i+1, end);
			check[i]=false;
		}
		
	}

	private static int cal(List<Integer> food) {
		int sum=0;
		int size=food.size();
		
		for (int i = 0; i < size-1; i++) {
			for(int j=i+1; j<size; j++) {
				sum+=foodInfo[food.get(i)][food.get(j)];
				sum+=foodInfo[food.get(j)][food.get(i)];
			}
		}
		return sum;
	}
}

 

소요시간 : 35분

 

조합만 쓸 줄 안다면 매우 쉬운 문제입니다.

 

주의하실 점은 만약 재료가 6개라면 (1,2,3,4,5,6)

1,2,3    4,5,6으로 나누었다고 치면

12 13   45 46 

21 23   54 56

31 33   65 64 

처럼 시너지를 구해야 한다는 점입니다!

 

우선 N/2를 depth로 해서 조합을 짭니다.

 

그렇게 해서 foodA, foodB를 만듭니다.

 

그리고 입력으로 주어진 시너지를 이용해서 값을 구해주면 끝입니다!!!