[ SWEA / 자바 ] 4012번 요리사

SW Expert Academy

SW Expert Academy

---

---

📑 문제

음식 재료 N개를 N/2개씩 두 개로 나누어 A음식과 B음식을 만드려고 한다

각 재료 별 시너지가 2차원 배열 S로 제시될 때, 재료 두가지 i,j가 만나 생기는 시너지는 S[i][j] + S[j][i]이다

각 음식의 맛은 재료들의 시너지 총합이다

A음식과 B음식 시너지 차의 절대값이 최소가 되는 경우를 출력하라

 

💡 입력

✔ 맨 첫 줄은 테스트케이스 개수

✔ 각 테스트 케이스의 첫 번째 줄에는 식재료의 수 N이 주어진다

✔ 다음 N개의 줄에는 N * N개의 시너지 Sij값들이 주어진다

✔ i와 j가 서로 같은 경우는 0으로 주어진다.

---

---

✨ 풀이과정

✔ 재료를 반으로 나누는 과정은 여러가지를 조합하되, 순서가 상관 없으므로 조합을 사용하였다

✔ 나눈 재료로 시너지를 탐색할 때는 순서가 중요하기 때문에 순열을 사용하였다

💥 실수한 부분

✔ 결과를 저장 변수 초기화는 재료 시너지 더하는 메서드 실행 이전에 해줘야 함

 

---

---

📑 코드

import java.util.Scanner;

public class Solution {
	static int N; //재료 개수
	static int[] Ns; //재료 번호가 담긴 배열
	static boolean[] check; //어떤 재료를 썼는지 판별하기 위한 배열
	static int food; //요리 하나당 쓰이는 재료 개수
	static int[] A; //A요리에 쓰는 재료
	static boolean[] checkA; //A에서 어떤 재료를 뽑았는지 판별하기 위한 배열
	static int[] a; //a 조합 결과 배열
	static int[] B; //B요리에 쓰는 재료
	static boolean[] checkB;
	static int[] b;
	static int[][] map; //시너지 
	static int resultA; //A요리 시너지 합
	static int resultB; //B요리 시너지 합
	static int ans; //정답
	
	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(); //재료 수
		
		Ns = new int[N];
		for(int i=1; i<=N; i++) {
			Ns[i-1] = i;
		}
		
		check = new boolean[N];
		
		food = N/2; //각 요리에 들어갈 재료 수
		A = new int[food];
		checkA = new boolean[food];
		B = new int[food];
		checkB = new boolean[food];
		
		a = new int[2];
		b = new int[2];
		
		map = new int[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		ans = Integer.MAX_VALUE;
		
		makeFood(0, 0);
		
		System.out.println("#"+tc+" "+ans);
		
		}
	}

	private static void makeFood(int idx, int sidx) { //조합
		//탈출조건
		if(sidx == food) {
			int bdx = 0;
			int adx = 0;
			for(int i=0; i<N; i++) {
				if(!check[i]) {
					B[bdx++] = Ns[i];
				} else {
					A[adx++] = Ns[i];
				}
			}
			resultA = 0;
			resultB = 0;

			// A = [] B = [] 여기까지 만들었고
			
			combination(0); //각 재료별 시너지를 더해봅시다
			
			ans = Math.min(ans, Math.abs(resultA-resultB));
			 
			return;
		} else if(idx >= N) return;
		else {
		
				makeFood(idx+1, sidx);
				check[idx] = true;
				makeFood(idx+1, sidx+1);
				check[idx] = false;
		}
	}

	//result를 만들어봅시다
	private static void combination(int idx) { //순열
		//탈출조건
		if(idx > 1) {

				resultA += map[a[0]-1][a[1]-1];
				resultB += map[b[0]-1][b[1]-1];

				return;
		}
		
		for(int i=0; i<food; i++) {
			if(!(checkA[i])) {
				a[idx] = A[i];
				b[idx] = B[i];
				checkA[i] = true;
				checkB[i] = true;
				combination(idx+1);
				
				checkA[i] = false;
				checkB[i] = false;
			}
		}
	}

}

---

---