[SWEA 4012 - Java] 요리사

SW Expert Academy

 

풀이

그냥 모든 경우의 수를 확인하면 되는 간단한 문제입니다!

첫 번째 재료부터 A요리 또는 B요리에 추가하면서 재귀를 호출하여 마지막 요리까지 모두 추가한 후에 시너지의 차를 계산하여 그 시너지 차의 최소를 출력하면 되는 문제입니다.

 

import java.util.Scanner;

public class Solution {
	
	static int N;
	static int[][] matrix;
	static int[] foodA;
	static int[] foodB;
	static int answer;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for(int tc = 1; tc<=T; tc++) {
			N = sc.nextInt();
			matrix = new int[N][N];
			answer = -1;
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					matrix[i][j] = sc.nextInt();
				}
			}
			
			foodA = new int[N/2];
			foodB = new int[N/2];
			
			addFood(0, 0, 0);
			
			System.out.println("#"+tc+" "+answer);
		}
	}
	
	//재귀로 재료 추가 
	static void addFood(int aCnt, int bCnt, int idx) {
		
		if(idx == N) {
			calcS();
		}
		
		//A에 재료 추가
		if(aCnt < N/2) {
			foodA[aCnt] = idx;
			addFood(aCnt+1, bCnt, idx+1);
		}
		
		//B에 재료 추가 
		if(bCnt < N/2) {
			foodB[bCnt] = idx;
			addFood(aCnt, bCnt+1, idx+1);
		}
		
	}
	
	// 시너지 계산 
	static void calcS() {
		int a = 0;
		int b = 0;
		
		for(int i=0; i<N/2; i++) {
			for(int j=0; j<N/2; j++) {
				a += matrix[foodA[i]][foodA[j]];
			}
		}
		
		for(int i=0; i<N/2; i++) {
			for(int j=0; j<N/2; j++) {
				b += matrix[foodB[i]][foodB[j]];
			}
		}
		
		int v = Math.abs(a-b);
		
		if(answer == -1 || answer > v)
			answer = v;
	}

}