[SWEA] 4012 요리사

4012 요리사

풀이)

문제 자체는 어렵지 않았다.

dfs를 이용해 각 음식마다 어떤 식쟤료를 가질건지 결정한 다음, 시너지 계산하는 완전 탐색 문제였다.

그런데 처음에 시간초과 나길래 당황했다.

알고보니, n개의 식재료가 있다면 음식 1을 위해 n/2 개까지만 고르고 나머지 쟤료들은 음식 2를 위해 쓰면되는데

쓸데없이 식재료 n개의 나올 수 있는 모든 조합을 다 보고 있었다.

즉, 음식 1을 위해 n/2개만 고르면 되는데 1~n개까지 고르는 경우를 다 확인한 것이다.

(그리고 나서 n/2개씩일때만 계산하게 함)

다시 풀때는 n/2개만 고르고 나머지들은 자동적으로 다른 음식 2를 위해 쓰이게 풀어줬다.

코드)

#include <stdio.h>
#include <vector>
#include<algorithm>
#include<cmath>
using namespace std;
 
#define INF 999999999;
 
int n;
int arr[16][16];
int result;
bool visited[16];
 
void dfs(int idx,int depth) {
    if (depth == n/2) {
        vector <int> food[2];
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                food[0].push_back(i);
            }
            else {
                food[1].push_back(i);
            }
        }
        int cnt[2] = { 0 ,0 };
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                if (i == j)continue;
                cnt[0] += arr[food[0][i]][food[0][j]];
                cnt[1] += arr[food[1][i]][food[1][j]];
            }
        }
        result = min(result, abs(cnt[0] - cnt[1]));
        return;
    }
    for (int i = idx; i < n; i++) {
        visited[i] = true;
        dfs(i + 1, depth + 1);
        visited[i] = false;
    }
}
 
int main() {
    //freopen("sample_input (1).txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
        result = INF;
        
        dfs(0, 0);
        printf("#%d %d\n", test_case, result);
    }
    return 0;
}