백준 14889 스타트와 링크

1. 문제를 명확하게 이해하고, 2 어떻게 구현할지 명확하게 합니다. 3. 팀을 이룬 사람들끼리 합을 어떻게 구할 것인지가 포인트입니다. 4. 조합은 기본!

/* 1830 시작 팀을 2개로 나누고, 1850 분 20분 컷!!! 조합으로 하고, */ #include <iostream> #include <algorithm> using namespace std; #define SIZE 21 int map[SIZE][SIZE]; int visit[SIZE]; int N; int team1, team2; int minVal = 2123456789; void problemIn() { cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> map[i][j]; } } } void dfs(int pos, int depth) { if (pos == N && depth == N / 2) { team1 = team2 = 0; for (int i = 0; i < N - 1; i++) { if (visit[i] == 1) { for (int j = i + 1; j < N; j++) { if (visit[j] == 1) { team1 += map[i][j]; team1 += map[j][i]; } } } } for (int i = 0; i < N - 1; i++) { if (visit[i] == 0) { for (int j = i + 1; j < N; j++) { if (visit[j] == 0) { team2 += map[i][j]; team2 += map[j][i]; } } } } minVal = min(minVal, abs(team1 - team2)); return; } if (pos == N) return; visit[pos] = 1; dfs(pos + 1, depth + 1); visit[pos] = 0; dfs(pos + 1, depth); } void solve() { dfs(0, 0); } int main() { problemIn(); solve(); cout << minVal << endl; return 0; }