/* 스타트링크 문제, 엔명은 짝수입니다. 쌍의 능력치의 합입니다. 팀의 능력치는 에스아이제이와 에스제이아이입니다. 엔은 4이고 에스가 아래와 같은 경우를 살펴보도록 하겠습니다. 1. 먼저 팀을 나누고, 엔이 4이면 4C2 로 01 02 03 12 23 이런식으로 나누게 됩니다. 오께이. 2. 나눈 팀에 대해서 합을 구하고 3. 능력치의 차이를 최소로 하기위해서, 팀1 합 - 팀2합 = 최소값을 찾는 것이 끝. */ #include <iostream> #include <algorithm> #define SIZE 21 using namespace std; int map[SIZE][SIZE]; int visit[SIZE]; int n, x, y, nx, ny; int team1, team2; int minVal=1000000000, diff; 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++) { for (int j = i + 1; j < n; j++) { if (visit[i] == 1 && visit[j] == 1) { team1 += map[i][j]; team1 += map[j][i]; } else if (visit[i] == 0 && visit[j] == 0) { team2 += map[i][j]; team2 += map[j][i]; } } } diff = abs(team1 - team2); minVal = min(minVal, diff); return; } if (pos == n) return; visit[pos] = 1; dfs(pos + 1, depth + 1); visit[pos] = 0; dfs(pos + 1, depth); } int main(void) { problemIn(); dfs(0, 0);
cout << minVal << endl; return 0; } |
맵과 비지트 이것은 조합알고리즘에서, 다음으로 예제를 정확하게 처리하는 것이 키포인트입니다. 예를 들어서 비지트 함수가 111000 으로 나뉘었을때, 저 안에서도 2개를 골라내야하는데 저는 이것을 조합으로만 풀려고 했습니다. 그것이 아니라 포문 2개 돌려서 찾을 수 있습니다. 3개를 골라야하면 포문을 3개 돌릴 수 있습니다. 일곱난쟁이도 이런식으로 풀이가 가능합니다. 오께이. 3개중에 2개를 골라야할 때, 2중 포문으로 골를 수 있다는 개념을 알고 있으면 됩니다. |