4012 요리사

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
 
using namespace std;
 
int num_food;
int food[20][20] = { 0 };
int teamA[20] = { 0 };
long long min_abs;
 
void combination(int idx, int depth);
int sum_abs();
 
int main() {
    int t;
    scanf("%d", &t);
 
    for (int test = 1; test <= t; test++) {
        min_abs = 1000000000000;
        scanf("%d", &num_food);
        memset(food, 0, sizeof(food));
        for (int i = 1; i <= num_food; i++) 
            for (int j = 1; j <= num_food; j++) 
                scanf("%d", &food[i][j]);
        
        for (int i = 1; i <= num_food - num_food / 2 + 1; i++) {
            teamA[i] = 1;
            combination(i, 1);                        
            teamA[i] = 0;
        }
        
        printf("#%d %d\n", test, min_abs);
    }
}
 
void combination(int idx, int depth) {
    if (depth == num_food / 2) {
        int tmp = sum_abs();
 
        if (tmp < min_abs)
            min_abs = tmp;
    }
    else {
        for (int i = idx + 1; i <= num_food; i++) {
            teamA[i] = 1;
            combination(i, depth + 1);
            teamA[i] = 0;
        }
    }
}
 
int sum_abs() {
    int sum_teamA = 0;
    for (int i = 1; i <= num_food; i++) 
        if (teamA[i] > 0) {
            int food_st = i;
            for (int j = 1; j <= num_food; j++) {
                if (teamA[j] > 0 && i != j)
                    sum_teamA += food[food_st][j];
            }
        }
    
    int teamB[20] = { 0 };
    for (int i = 1; i <= num_food; i++)
        if (teamA[i] == 0)
            teamB[i] = 1;
 
    int sum_teamB = 0;
    for (int i = 1; i <= num_food; i++)
        if (teamB[i] > 0) {
            int b_st = i;
            for (int j = 1; j <= num_food; j++)
                if(teamB[j]>0 && j!=b_st)
                    sum_teamB += food[b_st][j];
        }
 
    return abs(sum_teamA - sum_teamB);    
}

dfs 수열 문제랑 비슷하다

근데 아직도 리턴값이 있는 dfs 방식은 적응이 안 된다

이번에도 리턴값 있는 상태로 풀려고 했다가 잘못 생각한걸 깨닫고는 새로 풀이를 했다

익숙한 방식을 더 갈고 닦자