[SWEA] 4012. 요리사 (자바 JAVA)

[ 문제 ]  [SWEA] 4012. 요리사 (자바 JAVA)

 

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH 

SW Expert Academy

 

---

# 접근 방법 및 풀이 

 

• 조합으로 풀었다. 근데 조합코드보단 부분집합이 섞인..? 
• 식재료 수는 N 개고 짝수다. 이중 절반을 뽑아, 뽑은것은 A, 뽑지않은 것은 B로 나눠서 풀었다.
• 따라서 최대 N = 16일때, 8개를 뽑아야 하므로 16C8로 시간 안에 풀 수 있다.
• 시간초과가 난다면 2^16개를 다 뽑은 후 절반으로 나뉘어진거 추려내는 식으로 풀면 시간초과 난다.
• 2^16은 어후.. 재귀로 불가다. 최대 2^10정도가 돌아갈 듯.
• 중요한건 식재료를 뽑고 시너지의 합을 구하는 것인데, 문제에 식재료 2개로 하는걸로 밖에 안 나와있어서 약간 헷갈렸다.
• 시너지는 말 그대로 Sij를 다 구해야한다.
• 예를들어, 식재료 1, 3, 6을 뽑았다면, 다음과 같다.
• A = S[1][3] + S[1][6] + S[3][1] + S[3][6] + S[6][1] + S[6][3]
• 난 뽑을 식재료 배열을 check로 선언하고, 뽑은 것은 true로 해서 풀었다.
• 자세한건 코드참조

# 주의할 점 

 

• 시간초과 난다면 최대 2^16인 경우를 다 살펴보는지 체크하기

 

JAVA 코드

package 모의SW역량테스트;

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

public class swea_4012_요리사 {
	static int map[][], ans, N;
	static boolean check[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			ans = Integer.MAX_VALUE;
			N = Integer.parseInt(in.readLine());
			map = new int[N][N];
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(in.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			check = new boolean[N];
			comb(0, 0);
			System.out.println("#" + tc + " " + ans);
		}
	}

	private static void comb(int idx, int s_idx) {
		if (s_idx == N / 2) {
			int A = 0;
			int B = 0;
			for (int i = 0; i < N; i++) {
				if(check[i]) {
					for (int j = 0; j < N; j++) {
						if(check[j])
							A += map[i][j];
					}
				}else {
					for (int j = 0; j < N; j++) {
						if(!check[j])
							B += map[i][j];
					}
				}
			}
			int dif = Math.abs(A-B);
			ans = Math.min(ans, dif);
			return;
		}
		if (idx == N)
			return;
		check[idx] = true;
		comb(idx + 1, s_idx + 1);
		check[idx] = false;
		comb(idx + 1, s_idx);
	}
}

 

 

 

REVIEW