[백준]스타트링크(두번째)

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

첫번째 풀었을때는, 다른 코드를 보고 공부해서 풀었다.

두번째 풀었을 때는 15분 컷으로 풀었다... 뿌듯

먼저 들었던 생각은, 두개의 팀을 나눠야 한다는 것이었고 조합을 이용해야겠다 생각해서 dfs재귀를 이용하였다.

두팀이기 때문에 단순히 true/false로 나누어 주면 된다고 생각했고, true를 재귀를 통해 새겨준 후,

길이의 반이 되면 팀원끼리의 능력치를 더해주었다.

 

#include <iostream>
#include <cstring>
using namespace std;
/*
1.총 짝수명을 정확히 두그룹으로 나눈다. 능력치 차이의 최소값이 나오게한다.
2.완전탐색을 통해 len/2가 됐을때 표식을 해서 팀을 구분한다.
3.조합을 이용
*/
struct player {
    bool a;
};
 
player p[20];
int N;
int map[20][20];
int isV[20][20];
int ans = 1e9;//최소를 구해야함
 
void dfs(int start, int len) {
    if (len == N / 2) { 
        
        int start = 0, link = 0;//각 능력치
        
        for (int i = 0; i < N; i++) {
            if (p[i].a == true) { //true팀인 사람들끼리 합
                for (int j = 0; j < N; j++) {
                    if (p[j].a == true) {
                        start += map[i][j];
                    }
                }
            }
            if (p[i].a == false) {//false팀인 사람들끼리 합
                for (int j = 0; j < N; j++) {
                    if (p[j].a == false) {
                        link += map[i][j];
                    }
                }
            }
        }
        int a = abs(start - link);
        if (ans >= a) ans = a;
        return; 
    }
 
    //start를 통해 조합을 구현 뒤로만 진행
    for (int i = start; i < N; i++) {
        if (p[i].a == false) {
            p[i].a = true;
            dfs(i, len + 1);
            p[i].a = false;
        }
    }
}
 
int main()
{    
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
 
    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}