[SWEA 4012] 요리사

문제

• SWEA 4012
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

음식A,B를 N/2개씩 나누는것에서 출발하기 때문에 음식A를 만들게 되면 그 나머지는 B가 된다.
따라서, 음식A를 N/2개 만드는 조합을 재귀를 돌면서 selcted[]에 true표시하고, 자연스럽게 결정된 음식B와 함께 각각의 음식의 맛을 구한다. 현재 조합에서의 음식A와 B 각각의 음식의 맛은 totalA, totalB로 관리한다. 음식의 맛은 음식 2개의 시너지의 합이기 때문에 for문으로 모든 식재료를 돌면서 만약 selected[i] == true이면 음식A에 해당하는 식재료가 되고, 그 다음 음식A에 해당하는 식재료를 뽑아서 totalA에 저장한다. B도 마찬가지로 !selected[i] == true인 식재료를 2개 뽑아서 totalB에 저장한다. 이를 모두 반복해서 A의 음식의 맛과 B의 음식의 맛의 차의 절대값을 구하고 기존의 정답이 되는 Ans와 비교해 더 작으면 Ans에 저장해준다.

코드

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

//요리사
public class Solution {

	static int N; //식재료 수
	static int[][] table; //음식 시너지 정보, 1번부터 시작
	static boolean[] selected; //현재 뽑힌 음식A의 조합
	static int Ans; //정답: 최종 결정된 음식의 맛

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine()); // 테스트케이스의 개수
		StringTokenizer st;

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine()); 
			Ans = Integer.MAX_VALUE; //최대값으로 초기화
			table = new int[N+1][N+1]; //1~N
			for(int i=1; i<=N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=1; j<=N; j++) {
					table[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			selected = new boolean[N+1];
			//N/2개씩 음식A의 조합을 먼저 만들자 => 뽑고안뽑고 조합 사용!
			select(1, 0);
			System.out.println("#"+tc+" "+Ans);
		}
	}

	//selected배열에서 true인 식재료가 음식A임
	private static void select(int idx, int cnt) {
		
		if(cnt == N/2) { //N/2번 뽑았다면
			//현재 조합에서의 A,B의 음식의 맛 구하기, 1->2,2->1도 고려해야함
			int totalA = 0, totalB = 0; //A,B의 음식의 맛: 시너지들의 합
			
			//음식A의 식재료를 돌면서 두개를 뽑아 시너지를 누적합해서 음식의 맛 구하기
			for(int i=1; i<=N; i++) {
				if(selected[i]) { //음식A의 식재료라면
					for(int j=1; j<=N; j++) {
						if(selected[j]) { //또 다른 음식A의 식재료라면 
							totalA += table[i][j];
						}
					}
				}
				
				if(!selected[i]) { //음식B의 식재료라면
					for(int j=1; j<=N; j++) {
						if(!selected[j]) { //또 다른 음식B의 식재료라면
							totalB += table[i][j];
						}
					}
				}
			}
			Ans = Math.min(Ans, Math.abs(totalA - totalB));
		}
	
		if(idx == N) { //안뽑았는데 너무 많이 와버렸다면
			return;
		}
		
		selected[idx] = true; //뽑고
		select(idx+1, cnt+1); //뽑았음
		selected[idx] = false; //안뽑았음
		select(idx+1, cnt);
	}
}