SWEA 4012 - 요리사
Updated:
Java
4012 번 - 요리사
문제
N개의 식재료가 있다.
식재료들을 각각 N / 2개씩 나누어 두 개의 요리를 하려고 한다. (N은 짝수이다.)
이때, 각각의 음식을 A음식, B음식이라고 하자.
비슷한 맛의 음식을 만들기 위해서는 A음식과 B음식의 맛의 차이가 최소가 되도록 재료를 배분해야 한다.
음식의 맛은 음식을 구성하는 식재료들의 조합에 따라 다르게 된다.
식재료 i는 식재료 j와 같이 요리하게 되면 궁합이 잘 맞아 시너지 Sij가 발생한다. (1 ≤ i ≤ N, 1 ≤ j ≤ N, i ≠ j)
각 음식의 맛은 음식을 구성하는 식재료들로부터 발생하는 시너지 Sij들의 합이다.
식재료 i를 식재료 j와 같이 요리하게 되면 발생하는 시너지 Sij의 정보가 주어지고, 가지고 있는 식재료를 이용해 A음식과 B음식을 만들 때, 두 음식 간의 맛의 차이가 최소가 되는 경우를 찾고 그 최솟값을 정답으로 출력하는 프로그램을 작성하라.
접근 방법
n개의 식재료 중, n/2개씩의 식재료를 뽑아, 각각 n/2개의 시너지를 합한 요리 A, B의 차이를 구하는 문제이다.
즉, 총 6개의 재료가 있으며 A음식에 1, 2, 3번 재료가 들어가고, B음식에 4, 5, 6번 재료가 들어가면
A 요리 = 12 + 21 + 13 + 31 + 23 + 32 (음식 재료의 시너지)
B 요리 = 45 + 54 + 46 + 64 + 56 + 65 (음식 재료의 시너지)
가 된다.
- DFS를 통해 n개의 재료 중 n/2개를 뽑는다.
- 뽑은 n/2개의 재료중 나머지 재료들도 뽑는다.
- 각각 뽑은 재료들의 시너지 합을 구한다.
- 둘의 합 차이를 구하여 그 합의 차이 중 가장 최솟값을 구한다.
구현
DFS()
A의 요리에 넣을 재료들을 뽑는다.
DFS를 통해 재료들을 뽑은 뒤, 음식의 시너지 합을 계산하는 Cal()함수를 실행한다.
Cal()
먼저, B의 요리에 들어갈 재료들을 뽑아야한다.
DFS를 통해 재료들을 뽑을때 visited[] 배열을 사용하는데, 뽑은 재료들의 인덱스는 true이고 뽑히지 않은 재료는 false이다.
위 배열을 다시 한번 사용하여, visited[] 배열의 값 중, false인 재료들을 B의 요리에 들어가는 재료로 판단하여 따로 저장한다.
이제 sel[]에는 A 재료들의, nosel[]은 B의 재료들이 들어가 있으며 각각의 재료들의 합을 구한다.
[1,1], [2,2], [3,3]과 같이 인덱스가 동일한 시너지는 없으므로 continue를 통해 넘어간다.
두 합의 차를 구한 뒤, 함수 종료할 때, 값을 return한다.
그 값의 최소 값을 구한다.
코드
import java.io.*;
import java.util.*;
class Solution {
static int result = 987654321, n;
static int[][] synr;
static int[] sel, nosel;
static boolean[] vis;
public static void main(String []args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int tc = stoi(br.readLine());
for(int idx = 1; idx <= tc; idx++) {
result = 987654321;
n = stoi(br.readLine());
sel = new int[n / 2]; // A 요리 재료들
nosel = new int[n / 2]; // B 요리 재료들
vis = new boolean[n];
synr = new int[n][n]; // 재료들의 시너지 정보를 담을 배열
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < n; j++) {
synr[i][j] = stoi(st.nextToken());
}
}
DFS(0,0); // 계산 시작
System.out.println("#" + idx + " " + result);
}
}
// n/2개의 재료를 뽑는다.
static void DFS(int lv, int start) {
if(lv == n / 2) {
result = Math.min(Cal(), result); // 함수 계산 결과는 음식 간의 차이이며, 이 값의 최솟값을 구한다.
return;
}
for(int i = start; i < n; i++) {
if(!vis[i]) {
vis[i] = true;
sel[lv] = i;
DFS(lv + 1, i + 1);
vis[i] = false;
}
}
}
static int Cal() {
int diff = 0, Afood = 0, Bfood = 0, idx = 0;
// B의 요리에 들어갈 재료들을 뽑는다.
for(int i = 0; i < n; i++) {
if(!vis[i]) { // DFS를 통해 뽑을 때, 뽑히지 않은 재료들은 false이다
nosel[idx++] = i;
}
}
// A 음식의 시너지 합을 구한다
for(int i = 0; i < n / 2; i++) {
for(int j = 0; j < n / 2; j++) {
if(i == j)
continue;
Afood += synr[sel[i]][sel[j]];
}
}
// B 음식의 시너지 합을 구한다
for(int i = 0; i < n / 2; i++) {
for(int j = 0; j < n / 2; j++) {
if(i == j)
continue;
Bfood += synr[nosel[i]][nosel[j]];
}
}
diff = Math.abs(Afood - Bfood);
return diff;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
난이도
⭐⭐★★★
후기
뽑히지 않은 값들을 구하는데 잠시 어려움이 있었다.
뽑히지 않은 값들은 visited 배열을 재사용 하여 구할 수 있다는 것을 배운 문제이다.
개선할 점
없
