[BOJ] 14889번: 스타트와 링크, [SWEA] 4012번: 요리사

문제

SWEA(SW Expert Academy) 4012번- [모의 SW 역량테스트]요리사

백준 14889번-스타트와 링크
14889번: 스타트와 링크

풀이

A, B요리 각각 재료를 반씩 나눠가지기 때문에 A요리 재료를 선택한 후 남은 재료를 B요리에 사용 -> 조합

A요리에 선택된 재료의 정보는 isSelected 배열에 해당 인덱스를 true로 바꿔줌으로써 저장

조합 알고리즘에 기저조건을 재료가 N/2개 선택되었을 때로 정함

기저조건 달성 시, 현재 조합으로 맛을 비교하는 compTasty메소드 실행

현재 조합에서의 맛 차이(compTasty() 결과값)와 기존의 맛 차이 중 최솟값(tasty) 비교

코드

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

public class Solution{
	static int N;
	static int[][] arr;		//시너지 배열을 저장하는 변수
	static boolean[] isSelected;	//a조합에 선택된 재료 idx: true, b조합에 선택된 재료 idx: false
	static int tasty;	//결과 값(=최소 맛 차이)
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int tc = Integer.parseInt(br.readLine());	//테스트케이스 수
		for(int T=1 ; T<=tc ; T++) {
			N = Integer.parseInt(br.readLine());	//재료의 수
			arr = new int[N][N];
			for(int i =0 ; i < N ; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for(int j =0 ; j < N ; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());	//시너지 값 저장
				}
			}
			isSelected = new boolean[N];
			tasty = Integer.MAX_VALUE;
			comb(0,0);	
			sb.append("#").append(T).append(" ").append(tasty).append("\n");
		}
		System.out.println(sb.toString());
	}
	
	//재료의 조합을 결정하는 메소드
	static void comb(int cnt, int start) {
		if(cnt == N/2) {	//기저조건: 재료가 N/2개 선택되었을 때
			tasty = Math.min(tasty, compTasty());		//현재 조합으로의 맛 차이(compTasty()), 기존의 맛차이(tasty) 중 최솟값 선택
			return;
		}
		for(int i = start ; i < N ; i++) {		
			isSelected[i] = true;	//선택된 재료: true
			comb(cnt+1, i+1);	//다음자리 조합 뽑으러
			isSelected[i] = false;	//다음 조합에 영향을 주지 않기 위해 다시 초기화
		}
	}
	
	static int compTasty() {
		int[] a = new int[N/2] , b = new int[N/2];		// a, b 요리 재료의 idx를 저장하는 배열
		int a_idx = 0, b_idx = 0;		
		for(int i =0 ; i < N ; i++) {
			if(isSelected[i]) a[a_idx++] = i;		//조합에서 선택되었다면 a요리
			else b[b_idx++] = i;					//선택되지 않았다면 b요리
		}
		int a_ts = 0, b_ts =0;		//a, b 요리의 맛
		for(int i = 0 ; i < a.length ; i++) {
			for(int j = 0 ; j<a.length ; j++) {
				a_ts += arr[a[i]][a[j]];	//요리의 각 재료간의 시너지를 더함
				b_ts += arr[b[i]][b[j]];	
			}
		}
		return Math.abs(a_ts - b_ts);
	}
}