/* 먼저 팀을 나눕니다. 123 456 이면 123 / 456 팀 이렇게 말입니다. 비지트를 해서 111 000 이렇게 됬을 경우에 111 의 합을 구하는 것을 구현해보도록 하겠습니다. 인덱스 처리와 그런것들을 명확히 할 것. */ #include <iostream> #include <algorithm> using namespace std; #define SIZE 21 int map[SIZE][SIZE]; int visit[SIZE]; int n; int team_one; int team_two; int minVal=INT8_MAX; 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) { team_one = 0; team_two = 0;
for (int i = 0; i < n; i++) { if (visit[i] == 1) { for (int j = i + 1; j < n; j++) { if (visit[j] == 1) { team_one += map[i][j]; team_one += map[j][i]; } } } else { for (int j = i + 1; j < n; j++) { if (visit[j] == 0) { team_two += map[i][j]; team_two += map[j][i]; } } } } minVal = min(minVal, abs(team_one - team_two)); } 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; } |
일단 visit 에 대한 정보를 얻은뒤에, 그것을 어떻게 처리할가에 대한 고민을 하였으나, 그것보다 더 나은 풀이방법이 있었습니다. 그것을 찾기 위해서, 조합을 할 필요가 없고, 인덱스만 취하면 되므로.... 필요한 정보가 무엇인지 명확히 하는 것 이 필요합니다. 그리고 어디서 기능이 끝나는지 확인하도록 합니다. 저 부분을 하나의 함수로 만들어도 되겠습니다만,, 오께이. 저렇게 하고 다른 함수로 넘어가도 되겠습니다만, 지금 문제는 후의 풀이가 간단하므로 저렇게 넣어두도록 하겠습니다. 그리고 인덱스에 대해서 명확히 인지 하고 있도록 합니다. |