[SWEA][모의 SW 역량테스트][C++] 4012 요리사

문제

SWEA 모의 SW 역량테스트 - 4012 요리사

SW Expert Academy

 

---

문제 풀이

접근 방식

이 문제는 N(짝수) 개의 식재료를 반으로 나눠 두 개의 요리를 할 때,

두 요리의 총 시너지의 차가 최소가 되도록 조합하는 문제이다.

조합을 간단하게 구현하기 위해 next_permutation을 사용해주었다.

 

next_permutation에 인자로 넣을 벡터 idx는 N개의 0으로 초기화하고,

N/2개의 1을 뒤쪽부터 넣어주었다.(정렬할 필요가 없도록!)

do ~ while문 내에서는 0인 경우와 1인 경우로 나눠서 인덱스를 벡터에 저장하고,

그 인덱스들의 조합을 통해 각 요리의 총 시너지를 구해주었다.

(i == j인 경우, 시너지 값이 0이기 때문에 예외 처리 없이 더해줘도 된다.)

abs를 사용하여 두 시너지의 값의 차를 구하고, 이를 활용하여 최솟값을 찾아주었다.

 

---

풀이 코드 - C++

#include<iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(int argc, char** argv)
{
    int test_case;
    int T, N;
 
    // freopen("input.txt", "r", stdin);
    cin >> T;
 
    for (test_case = 1; test_case <= T; ++test_case) {
        cin >> N;
        vector<vector<int>> S(N, vector<int>(N));
        for (int i = 0; i < N; i++)  {
            for (int j = 0; j < N; j++)  {
                cin >> S[i][j];
            }
        }
        vector<bool> idx(N);
        for (int i = 0; i < N / 2; i++) {
            idx[N - i - 1] = 1;
        }
        int MIN = 987654321;
        do {
            int sum1 = 0;
            int sum2 = 0;
            vector<int> num1;
            vector<int> num2;
            for (int i = 0; i < N; i++)  {
                if (idx[i] == 1) {
                    num1.push_back(i);
                }
                else {
                    num2.push_back(i);
                }
            }
            for (int i = 0; i < N/2; i++) {
                for (int j = 0; j < N/2; j++) {
                    sum1 += S[num1[i]][num1[j]];
                    sum2 += S[num2[i]][num2[j]];
                }
            }
            int result = abs(sum1 - sum2);
            if (MIN > result)
                MIN = result;
        } while (next_permutation(idx.begin(), idx.end()));
 
        cout << "#" << test_case << " " << MIN << endl;
    }
    return 0;
}

실행 결과