개요
조합의 조합을 생각하는 문제, 재료의 시너지를 조금 고민하게 되는 문제였다.
문제분석
문제는 두가지 방식으로 풀었다. 크게 다르지는 않고,재료의 시너지를 구하는 방법이 조금 다르다.
일단, 문제를 분석해보자.
식재료 N개가 주어지고,두명의 요리사가 식재료를 반씩 나누어 선택한다.
이때, 식재료끼리의 시너지 (=맛)을 가지고 있는 2차원 배열을 이용하여 두가지 요리의 맛을 구해야하며, 그 맛의 차이가 최소가 되는 값을 찾아야한다.
처음으로,식재료를 선택하는 과정의 경우, 간단하게 조합을 통해 구해줄 수 있다.
나의 경우, 선택하고 선택하지 않고를 나누어서 들어가는 코드를 사용했다.
해당 코드를 수도코드로 작성해보면 다음과 같다
함수 ( 선택한 갯수 , 선택배열)
만약 선택한 갯수가 N이라면,
리턴한다
선택배열 [ 선택한 갯수 ] = 1 // 1번 요리사가 해당 재료를 선택함
함수 (선택한 갯수 + 1 , 선택 배열)
선택배열 [선택한 갯수] = 2 // 2번 요리사가 해당 재료를 선택함
함수 (선택한 갯수 + 1 , 선택배열)
이런 형식 외에도 for문을 이용한 형식이 있을 수 있다 이것 또한 수도코드로 작성해보면 다음과 같다.
함수( 선택한 갯수 , 선택배열 , 방문 배열)
만약,선택한 갯수가 N과 같다면
리턴한다
반복문 ( i = 1 부터 데이터배열의 길이만큼 반복한다 )
만약,방문배열 [i]를 방문했다면, 다음 반복문으로 간다
선택배열[선택한 갯수] = 데이터배열[i]
방문배열[i] = 참
함수(선택한 갯수 + 1 , 선택배열 , 방문배열)
방문배열[i] = 거짓
개인적으로는 첫번째 형식의 코드를 좋아하지만, 상황에 따라 다르게 구성하한다.
선택하고 선택하지 않는 경우를 나누어서 해주는 것
여기에서 중복이 가능하게 하려면 방문배열을 빼주면 된다.
본론으로 들어가서 문제의 구성을 짜보자.
1.요리사가 선택하는 재료의 조합을 구성한다.
2.요리사가 선택한 재료의 시너지를 구한다.
시너지를 구하는 과정에서 고민이 많았다. 재료를 두개만 선택할 경우에는 단순하지만, 두개 이상이면 고민이 생긴다.
1 2 3 4 5 6 이 있다고 가정할때, 요리사 1이 (1,2,3) 요리사 2가 (4,5,6) 를 선택했다고 해보자.
요리사 1의 음식이 가지는 시너지를 계산해보면 다음과 같다.
1,2 1,3 2,1 2,3 3,1 3,2 -> 어디서 본 형태가 아닌가 ? 맞다, 바로 조합이다.
아,,그러면 여기서 또 두개 선택하는 경우의 수를 구해야하나? 아니다 바로 이중 for문을 통해서 충분히 구할 수 있다.
여기에서 1,2 2,1 은 같은 시너지가 아님을 명심해야한다.
이중 for문을 사용했을때, 안과 밖의 변수가 동일한 경우만 빼면 시너지를 모두 구할 수 있다.
즉, 다음과 같다
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i == j) continue;
// 여기에다가 코드를 작성하면 된다
}
}만약 1,2 와 2,1이 같은 경우일 경우, j를 i보다 크게 맞추어 주면된다. 그러면 자연스럽게 앞숫자 보다 뒷숫자가 크게 될 것이다.
본격적으로 문제풀이를 보자
문제풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* @see
* @since 11/25/23
**/
public class Solution {
static int T,N,answer;
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int t=1;t<T+1;t++){
N = Integer.parseInt(br.readLine());
map = new int[N][N];
answer = Integer.MAX_VALUE;
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<N;j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0,new int[N]);
System.out.printf("#%d %d\n",t,answer);
}
}
//식재료 0,1,2,3..를 누가 선택했는지 (0,1)
static void dfs(int depth,int[] selected){
if(depth == N){
//모든 식재료 다 선택
//식재료가 반반 선택되었는지 확인하기
int cnt = 0;
for(int value : selected){
if(value == 0) cnt++;
}
if(cnt != N/2) return; // 식재료가 반반 선택된게 아님
ArrayList<Integer> a = new ArrayList<>();
ArrayList<Integer> b = new ArrayList<>();
for(int i=0;i<selected.length;i++){
if(selected[i] == 0) a.add(i);
else b.add(i);
}
int food_a = 0;
int food_b = 0;
for(int i=0;i<N/2;i++){
for(int j=0;j<N/2;j++){
if(i == j) continue;
food_a += map[a.get(i)][a.get(j)];
food_b += map[b.get(i)][b.get(j)];
}
}
answer = Math.min(Math.abs(food_a-food_b),answer);
return;
}
selected[depth] = 0;
dfs(depth+1,selected);
selected[depth] = 1;
dfs(depth+1,selected);
}
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* @see
* @since 11/28/23
**/
public class Solution {
static int T,N;
static int[][] map;
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int t=1;t<T+1;t++){
N = Integer.parseInt(br.readLine());
map = new int[N][N];
answer = Integer.MAX_VALUE;
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<N;j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0,new int[N]);
System.out.printf("#%d %d\n",t,answer);
}
}
static void dfs(int depth,int[] selected){
if(depth == N){
ArrayList<Integer> arr1 = new ArrayList<>();
ArrayList<Integer> arr2 = new ArrayList<>();
for(int i=0;i<selected.length;i++){
if(selected[i] == 1) arr1.add(i);
else arr2.add(i);
}
int food1 = 0;
int food2 = 0;
if(arr1.size() == N/2 && arr2.size() == N/2) {
for(int i=0;i<N/2;i++){
for(int j=i+1;j<N/2;j++){
food1 += map[arr1.get(i)][arr1.get(j)] + map[arr1.get(j)][arr1.get(i)];
food2 += map[arr2.get(i)][arr2.get(j)] + map[arr2.get(j)][arr2.get(i)];
}
}
answer = Math.min(answer,Math.abs(food1-food2));
return;
}
return;
}
selected[depth] = 1;
dfs(depth+1,selected);
selected[depth] = 2;
dfs(depth+1,selected);
}
}개인적으로는 첫번째 코드가 더 깔끔한 것 같다.
재료의 시너지를 구하는 코드가 좀 더 깔끔해보이고 직관적이기 때문이다.
사실 비슷비슷하지만...
