[SW Expert 4012] 요리사

[문제 바로가기]👇

SW Expert Academy

 

💡풀이💡

1. N개의 요리 중에서 N/2개의 재료를 골라 요리 A, B 만들기

N/2개를 골라 요리를 만들면, 고르지 않은 나머지 N/2개가 다른 쪽 요리의 재료가 됨! 각 요리의 합을 구하는 것이기 때문에 순서가 x
>> 따라서 조합!! 

 

2. 요리의 재료가 완성 되었을 때(조합이 완성 되었을 때) 각 요리 맛의 최솟값 구하기

 

1. 입력 받기

	static int[][] data;
	static int N ,R;
	static boolean[] v; // 완성된 조합 저장
	static int min;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			R = N/2; // N/2를 계산해서 변수에 미리 저장
			data = new int[N][N];
			v = new boolean [N];
			min = Integer.MAX_VALUE;
			
			for(int i=0; i<N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for(int j=0; j<N; j++) {
					data[i][j] = Integer.parseInt(st.nextToken());
				}
			}

 

2. 요리 재료 조합 구하기

조합이 완료 되었을 때(cnt == R) 각 요리의 맛 최솟값을 계산!

• 조합이 완성 되었을 때, 선택되지 않은 나머지는 무조건 다른 요리의 재료가 되기 때문에 int형 배열로 R개 만큼 생성하지 않고 boolean형으로 N개 만큼 생성함

📌놓쳤던 포인트!

• 기존의 조합 코드에서는 완성될 조합을 저장할 배열을 R개만큼 생성해 b[cnt] = a[i] 라는 형식으로 했었다.
• 완성될 조합을 저장할 때 boolean형 배열에 선택됐는지 확인하기 때문에 v[cnt]가 아니라 v[i]로 true 체크를 해줘야 함
• v[cnt] 로 하면 cnt 최댓값이 R이기 때문에 0,1 인덱스의 재료만 선택이 됨ㅠㅠㅠ…

static void comb(int cnt, int start) {
		if(cnt == R) {
			// 맛  최솟값 계산하기
			min = cal_flavor();
		}
		
		for(int i=start; i<N; i++) {
			v[i] = true;
			comb(cnt+1, i+1);
			v[i] = false;
		}
}

 

3. 맛 최솟값 계산하기

둘 다 true일 때를 A요리 , 나머지 둘 다 false일 때를 B요리 재료라고 생각하고 각각의 맛의 합 구하기

둘의 차의 최솟값을 리턴

static int cal_flavor() {
	int aSum = 0;
	int bSum = 0;
		
	for(int i=0; i<N; i++) {
		for(int j=i+1; j<N; j++) {
			if(v[i] && v[j]) aSum += data[i][j] + data[j][i];
			else if(!v[i] && !v[j]) bSum += data[i][j] + data[j][i];
		}
	}
	int minFlavor = Math.min(min, Math.abs(aSum-bSum));
	return minFlavor;
}

 

 

4. 전체 코드

package ps_0215;

import java.io.*;
import java.util.*;

public class SW4012 {
	static int[][] data;
	static int N ,R;
	static boolean[] v;
	static int min;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			R = N/2;
			data = new int[N][N];
			v = new boolean [N];
			min = Integer.MAX_VALUE;
			
			for(int i=0; i<N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for(int j=0; j<N; j++) {
					data[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			comb(0,0);
			sb.append("#").append(tc).append(" ").append(min).append("\\n");
		}
		System.out.println(sb.toString());
		br.close();
	}
	
	static void comb(int cnt, int start) {
		if(cnt == R) {
			// 맛  최솟값 계산하기
			min = cal_flavor();
		}
		
		for(int i=start; i<N; i++) {
			v[i] = true;
			comb(cnt+1, i+1);
			v[i] = false;
		}
	}
	
	static int cal_flavor() {
		int aSum = 0;
		int bSum = 0;
		
		for(int i=0; i<N; i++) {
			for(int j=i+1; j<N; j++) {
				if(v[i] && v[j]) aSum += data[i][j] + data[j][i];
				else if(!v[i] && !v[j]) bSum += data[i][j] + data[j][i];
			}
		}
		int minFlavor = Math.min(min, Math.abs(aSum-bSum));
		return minFlavor;
	}
}