(Java/자바) - SWEA [모의 SW 역량테스트] 4012번 : 요리사

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH 

SW Expert Academy

---

• 문제 : 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

 

 

 

---

• 풀이 :

조합 문제였습니다.

 

1 부터 n번까지의 식재료 중 n/2개를 선택하여 해당 재료로 만든 요리의 맛과, 나머지 n/2개의 재료로 만든 요리의 맛의 차이를 최소화하는 문제입니다.

 

풀이입니다.

 

1. N개의 재료 중 N/2개의 재료를 선택하는 모든 경우를 탐색합니다.

 

2. 각 경우마다 N/2개의 재료를 선택한 경우의 맛과 나머지 N/2개를 선택한 경우의 맛의 점수를 계산합니다.

 

3. 이 값을 최솟값으로 갱신합니다.

 

추가 ) 어짜피 ingredients의 i,j와 j,i를 더해줘야 하기 때문에 입력을 받을 때 i,j에 모아두었습니다.

 

 

 

---

• 소스코드 : 

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

public class Solution{
	static int TC;
	static int N;
	static int[][] ingredents;
	static boolean[] selected;
	static int answer;
	static int tmp;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		TC = Integer.parseInt(br.readLine());
		
		// 입력받기, 어짜피 [i,j] + [j, i] 할 것이므로 [i,j]에 미리 더해놓음
		for (int testCase = 1; testCase <= TC; testCase++) {
			N = Integer.parseInt(br.readLine());
			answer =Integer.MAX_VALUE;
			ingredents = new int[N][N];
			selected = new boolean[N];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					tmp = Integer.parseInt(st.nextToken());
					if (j > i) ingredents[j][i] += tmp;
					else ingredents[i][j] += tmp;
				}
			}
			
			
			solution(0, 0);
			sb.append("#"+testCase+" ").append(answer + "\n");
		}
		System.out.println(sb.toString());
	}
	public static void solution(int cnt, int start) {
		// N/2개를 골랐을 경우 
		if (cnt == N/2) {
			tmp = 0;
			for (int i = 0; i < N-1; i++) {
				for (int j = i+1; j < N; j++) {
					
					// 둘다 상대방 요리에 들어가는 재료일 경우 
					if(!selected[i]&& !selected[j]) {
						tmp += ingredents[j][i];
						
					}
					// 둘다 내 요리에 들어가는 재료일 경우
					else if (selected[i] && selected[j]){
						tmp -= ingredents[j][i];
					}
				}
			}
			// 정답 최솟값으로 갱신
			answer = Math.min(answer,Math.abs(tmp));
			return;
		}
		
		// 조합 탐색
		for (int i = start; i < N; i++) {
			selected[i] = true;
			solution(cnt+1, i  + 1);
			selected[i] = false;
		}
	}

}