[C++] SWEA 4012 - 요리사

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH&categoryId=AWIeUtVakTMDFAVH&categoryType=CODE&problemTitle=4012&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

<풀이>

1. A음식과 B음식을 만들 식재료를 분배한다.

2. 각 음식의 시너지 합을 구하고 그 차이가 최소가 되는 값을 출력한다.

 

<해법>

1. 식재료를 분배하는 방법

=> 식재료 중 절반을 선택해서 A음식에 사용하고, 선택하지 않은 나머지 절반을 B음식에 사용하도록 합니다. 간단히 생각하면, N개 중에서 N/2개를 고르는 조합 문제입니다. 저는 재귀를 이용해서 구현하였습니다.

 

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#define INF 9876543321
 
using namespace std;
 
int N;
int S[16][16];
vector<int> a;
vector<int> b;
bool selected[16];
int answer;
 
int calculateTasteDiff() {
 
    int aTaste = 0, bTaste = 0;
 
    for (int i = 0; i < N / 2; i++) {
        for (int j = 0; j < N / 2; j++) {
            aTaste += S[a[i]][a[j]];
            bTaste += S[b[i]][b[j]];
        }
    }
 
    return abs(aTaste - bTaste);
}
 
void setiing() {
    a.clear(), b.clear();
    for (int i = 0; i < N; i++) {
        if (selected[i]) {
            a.push_back(i);
        }
        else {
            b.push_back(i);
        }
    }
}
 
void divideIngredient(int start, int cnt) {
 
    if (cnt == N / 2) {
        setiing();
        int tasteDiff = calculateTasteDiff();
        answer = min(answer, tasteDiff);
        return;
    }
 
    for (int i = start; i < N; i++) {
        selected[i] = true;
        divideIngredient(i + 1, cnt + 1);
        selected[i] = false;
    }
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0;
        memset(S, 0, sizeof(S));
        a.clear();
        b.clear();
        memset(selected, false, sizeof(selected));
        answer = INF;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> S[i][j];
            }
        }
 
        //해법
        divideIngredient(0, 0);
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

재귀함수에 대해 알아볼 수 있는 문제였습니다.