[모의 SW 역량테스트] 4012. 요리사

[모의 SW 역량테스트] 요리사

---

1. 이해하기

• N개의 식재료가 있고 식재료들을 각각 N/2개씩 나누어 두 개의 요리를 하려고 한다.(N은 짝수)
• 비슷한 맛의 음식을 만들기 위해서는 맛의 차이가 최소가 되도록 재료를 배분해야 한다.
• 식재료 i는 j와 같이 요리하게 되면 궁합이 잘 맞아 시너지 Sij가 발생한다.
• 각 음식의 맛은 음식을 구성하는 식재료들로부터 발생하는 시너지 Sij들의 합이다.
• 두 음식 간의 맛의 차이가 최소가 되는 경우를 찾고 그 최솟값을 정답으로 출력하는 문제.
• 완전탐색 문제.

---

2. 구현하기

• N/2개를 선택했을 때, 각 시너지들의 합을 구한다.

  int get_synergy(bool flag) {
      int ret = 0;
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              if(selected[i] == flag and selected[j] == flag) ret += map[i][j];
          }
      }
      return ret;
  }

• 음식의 맛 차이의 최솟값을 구한다.

  int solve(int index, int select_cnt) {
      if(index == N) {
          if(select_cnt == N/2) {
              int s1 = get_synergy(true), s2 = get_synergy(false);
              return abs(s1-s2);
          } else return MAX;
      }
  
      int ret = MAX;
      selected[index] = true;
      ret = min(ret,solve(index+1,select_cnt+1));
      selected[index] = false;
      ret = min(ret,solve(index+1,select_cnt));
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 987654321;
int map[16][16];
bool selected[16];
int N;

int abs(int a) {
    return (a<0)?-a:a;
}

int get_synergy(bool flag) {
    int ret = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(selected[i] == flag and selected[j] == flag) ret += map[i][j];
        }
    }
    return ret;
}

int solve(int index, int select_cnt) {
    if(index == N) {
        if(select_cnt == N/2) {
            int s1 = get_synergy(true), s2 = get_synergy(false);
            return abs(s1-s2);
        } else return MAX;
    }

    int ret = MAX;
    selected[index] = true;
    ret = min(ret,solve(index+1,select_cnt+1));
    selected[index] = false;
    ret = min(ret,solve(index+1,select_cnt));
    return ret;
}

void input() {
    memset(selected,false,sizeof(selected));
    cin >> N;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
}

int main() {
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        cout << '#' << t << ' ' << solve(0,0) << '\n';
    }
    return 0;
}