[SWEA/구현] 4012: [모의 SW역량 테스트] 요리사

문제

---

문제링크

SW Expert Academy

 

풀이

---

문제를 잘 읽어보지 않아 시간이 오래 걸린 문제...

문제에서 예제로 재료가 4개일 때 선택된 재료 2개와 선택되지 않은 재료 2개의 시너지를 각각 비교하여 

두음식간의 맛의 차이가 가장 작은 것을 구하는 것으로 예시를 들었다.

그래서 조합으로 N개의 재료중에서 2개를 뽑아서 시너지를 구하려고 하였다.

 

그런데 음식 재료가 4개가 아닌 값이 N개의 재료가 들어왔을 때  N/2 의 재료를 사용하여 선택되지 않은 나머지 재료를 N/2와 비교하는 문제였다.

즉, N_C_N/2 경우의 수에서 시너지를 구하는 문제다.. 

 

코드는 다음과 같다. 

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

public class SWEA_4012 {
	static int N, R;
	static boolean[] check;
	static int[] nums, otherNums;
	static int[][] fruit;
	static int ans = 0;
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	public static void main(String[] args) throws IOException {
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc <= T; tc++) {
        	// 입력
			N = Integer.parseInt(br.readLine());
			
			ans = Integer.MAX_VALUE;
			R = N/2;
			check = new boolean[N+1];
			nums = new int[R];
			otherNums = new int[R];
			fruit = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) fruit[i][j] = Integer.parseInt(st.nextToken());
			}
			// 입력 끝
            
			combination(0, 0);
			System.out.printf("#%d %d\n",tc, ans);
		}
	}
	
	// 재료의 조합 구하기
	public static void combination(int cnt, int start) {
		if(cnt == R) {;
			getOtherNums();
			solution();
			return;
		}
		for(int i = start; i < N; i++) {
			nums[cnt] = i;
			combination(cnt+1, i+1);			
		}
	}
	
    // 선택되지 않은 재료 구하기
	public static void getOtherNums() {
		int idx = 0;
		for(int i = 0; i < N; i++ ) {
			boolean flag = true;
			for(int j = 0; j < R; j++) if(i == nums[j]) flag = false;
			if(flag) otherNums[idx++] = i;
		}
	}
	
    // 시너지 구하기
	public static void solution() {
		int a = 0;
		int b = 0;
		for(int i = 0; i < R; i++) {
			for(int j = i+1; j< R; j++ ) {
				a += fruit[nums[i]][nums[j]] + fruit[nums[j]][nums[i]];
				b += fruit[otherNums[i]][otherNums[j]] + fruit[otherNums[j]][otherNums[i]];
			}
		}
		int diff = Math.abs(a-b);
		if(ans > diff) ans = diff;
	}
}

 

비트마스크 이용

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

public class SWEA_4012 {
	static int N;
	static int[][] map;
	static int total;
	static int minDifference;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			total = 0;
			minDifference = Integer.MAX_VALUE;
			for(int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					total += map[i][j];
				}
			}
			comb(0,0,0,0,total);
			System.out.println("#"+t+" "+minDifference);
		}
	}

	private static void comb(int depth, int start, int flag, int sum, int total) {
		// TODO Auto-generated method stub
		if(depth == N/2) {
			minDifference = Math.min(minDifference, Math.abs(sum - total));
			return;
		}
		
		for(int i = start; i < N; i++) {
			if((flag & 1<<i)!=0)	continue;
			int add = 0;
			int sub = 0;
			for(int j = 0; j < N; j++) {
				sub += map[i][j] + map[j][i];
				if((flag & 1<<j)!=0)
					add += map[i][j] + map[j][i];
			}
			comb(depth+1, i+1, (flag | 1<<i), sum + add, total - sub + add);
		}
	}
}