4012.요리사

이번에 풀어볼 문제는 SW Expert의 4012번 요리사이다.

SW Expert Academy

지금까지 풀었던 SW Expert 문제 중에 문제가 가장 애매하게 출제된 거 같다. 

그 이유는 식재료에 대한 중복내용이 없기 때문에 어떻게 풀어아햐는건지 확실하지 않다고 느꼈기 때문이다.

하여튼 간에 문제를 처음 읽어보면 어떤 부분이 애매한지 느낄 수 있을 것이다.

애매한 부분만 빼면 재귀함수를 연습하기에는 괜찮은 문제인 거 같다 => 나는 재귀를 잘못해서 조금 골치아팠다..

 

---

 

이 문제는 결론적으로 조합 문제이다. 결국 시너지를 만들어 내기 위함인데 두 가지의 조합이 들어가있다.

 

1. 음식A와 B에 대한 조합

=> 식재료의 갯수의 / 2를 선택하는 조합을 우선 구현해야한다.

=> 예를 들어 6가지의 식재료가 있다고하면 6개중 6/2 => 3개 즉 6개중 3개를 고르는 조합을 구현해야한다.

 

2. 그렇게 고른 3개의 식재료중 2개를 선택하는 조합

=> 3개중에 2개를 이용한 조합을 통해서 시너지의 크기를 구해야한다.

 

나는 재귀함수를 이용해서 조합을 만들었다.

개인적으로 식재료를 나눈거까지는 금방했는데 2번을 구현하는게 머리에 안떠올랐다..

이런 부분이 부족한 거 같다.. 부족한 부분을 찾아서 다행이다.

=> 정답을 보면 이걸 왜 못떠올렸나 싶다..( 21 ~ 27번 라인 )

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <deque>
#include <algorithm>
 
#define MAX 17
 
using namespace std;
 
int T, N;
int map[MAX][MAX]; // 식재료 map
bool check[MAX];   // 식재료 사용여부
int ans, syn;
int sum1, sum2; // 음식A, 음식B의 시너지 변수
 
deque<int>d1; // 음식 A의 식재료 그릇
deque<int>d2; // 음식 B의 식재료 그릇
 
void cook(){
    sum1 = sum2 = 0; // 0으로 초기화
    for (int i = 0; i < syn; i++){
        for (int j = 0; j < syn; j++){
            if (i != j ){
                sum1+=map[d1[i]][d1[j]]; // 음식 A의 시너지 구하기
            }
        }
    }
    for (int i = 0; i < syn; i++){
        for (int j = 0; j < syn; j++){
            if (i != j){
                sum2 += map[d2[i]][d2[j]]; // 음식 B의 시너지 구하기
            }
        }
    }
    d1.clear(); // 음식A의 식재료 그릇 비우기
    d2.clear(); // 음식B의 식재료 그릇 비우기
    ans = min(ans, abs(sum1 - sum2)); // 시너지의 차이 중 최소 값을 저장
}
 
void search(int start, int cnt){ // 시작 index와 고른 식재료의 개수를 인자로 조합 진행
 
    if (cnt == syn){  // 총 식재료중 절반을 골랐다면
        for (int i = 0; i < N; i++){ 
            if (check[i])
                d1.push_back(i); // 음식A에 선택한 식재료 저장
            else
                d2.push_back(i); // 남은 식재료는 음식B에 사용되므로 따로 저장
        }
        cook(); // 음식만들기 시작! ( 고른 식재료들로 최대 시너지를 찾는 함수 )
        return;
    }
    
    for (int i = start; i < N; i++){ // 인자로 넘겨준 시작 idx를 사용하는것이 Point !!
        // 식재료 조합 재귀함수
        if (!check[i]){         // 고른적이 없다면
            check[i] = true;    // 고른다
            search(i, cnt + 1); // 고른 갯수 +1
            check[i] = false;   // 다음 탐색을 위해 고른것 취소
        }
    }
}
 
int main() {
    freopen("4012.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        cin >> N;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                cin >> map[i][j];
            }
        }
        ans = 987654321; // 정답변수
        syn = N / 2;     // 식재료의 절반만 이용하여 시너지를 내야함
        search(0,0);     // 조합시작
        cout << "#" << z << " " << ans << endl;
    }
    return 0;
}