[SWEA] 4012 요리사 (D0 / 조합) - Java

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH&categoryId=AWIeUtVakTMDFAVH&categoryType=CODE&problemTitle=%EC%9A%94%EB%A6%AC%EC%82%AC&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

문제 해석

- 문제 해석

두 명에게 음식을 제공
N개의 식재료가 있으며, 식재료들을 N/2로 나누어 두 개의 요리를 함
두 음식의 맛의 차이가 최소가 되도록 해야함

식재료1과 식재료2를 함께 사용하면 시너지가 발생함
음식 1의 맛 : 시너지[1][2] + 시너지[2][1]

맛의 차이 : |음식1의 맛 - 음식2의 맛|

맛의 차이가 최소가 될때 맛의 차를 출력하라


- 각 테스트 케이스 별 입력
첫 번째 줄 : N # 음식 재료 개수
나머지 줄 : N줄의 시너지 정보

 

 

 

코드

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

public class Solution2 {
	static int[][] synergy;
	static int nowATaste;
	static int nowBTaste;
	static int answer;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int T = Integer.parseInt(st.nextToken());

		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());

			int N = Integer.parseInt(st.nextToken());

			synergy = new int[N][N];

			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					synergy[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			nowATaste = 0;
			nowBTaste = 0;
			answer = Integer.MAX_VALUE;
			recursive(new int[N / 2], 0, 0);

			System.out.println("#" + test_case + " " + answer);

		} // [E] test_case
	}

	private static void recursive(int[] sel, int aIdx, int sIdx) {
		// basis part
		if (sIdx == synergy.length / 2) {
			// 음식 a의 식재료 : sel

			// 음식 b의 식재료 : bSel
			int[] bSel = new int[synergy.length / 2];

			boolean[] v = new boolean[synergy.length];
			for (int i = 0; i < sel.length; i++) {
				v[sel[i]] = true;
			}

			int bIdx = 0;
			for (int i = 0; i < v.length; i++) {
				if (v[i] == false) {
					bSel[bIdx] = i;
					bIdx++;
				}
			}

			// 음식 시너지 찾기
			sRecursive(sel, new int[2], 0, 0, 'a');
			sRecursive(bSel, new int[2], 0, 0, 'b');

			// compare
			if (answer > Math.abs(nowATaste - nowBTaste)) {
				answer = Math.abs(nowATaste - nowBTaste);
			}
			nowATaste = 0;
			nowBTaste = 0;

			return;
		}

		// inductive part
		for (int i = aIdx; i < synergy.length; i++) {
			sel[sIdx] = i;
			recursive(sel, i + 1, sIdx + 1);
		}
	}

	private static void sRecursive(int[] arr, int[] sel, int aIdx, int sIdx, char type) {
		// basis part
		if (sel.length == sIdx) {
			if (type == 'a') {
				nowATaste += synergy[sel[0]][sel[1]] + synergy[sel[1]][sel[0]];
			}
			if (type == 'b') {
				nowBTaste += synergy[sel[0]][sel[1]] + synergy[sel[1]][sel[0]];
			}
			return;
		}

		// inductive part
		for (int i = aIdx; i < arr.length; i++) {
			sel[sIdx] = arr[i];
			sRecursive(arr, sel, i + 1, sIdx + 1, type);
		}
	}
}

 

 

 

코드 해석

중복이 없고, 순서 상관 없기 때문에 조합으로 풀 수 있는 문제입니다.

 

먼저 N/2개의 음식을 골라야하므로 조합을 한 번 사용하게 되며, 이후 선택된 음식들을 다시 한 번 조합을 통해 시너지를 얻어내야 합니다. 즉 2번의 조합이 이뤄질 수 있도록 코드를 구현해야 합니다.

 

 

 

발생한 문제 & 해결 방안

해당 문제를 앞서 풀어본 많은 사람들과 마찬가지로 문제의 이해를 음식을 만드는데 2개의 음식만을 사용해야 하는 줄 알고 오랫동안 헤매였습니다.

 

테스트 케이스에서 명확하게 설명하지 않은 부분도 존재하지만, 문제를 정확하게 읽고 이해한 후 푸는 것이 매우 중요하다고 깨달았습니다.

 

증감식을 제대로 작성하지 않아 오류가 발생하였습니다.

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice