#include <iostream> #include <algorithm> using namespace std; int map[21][21]; int visit[21]; int n, ans = INT_MAX; int getAbility(int *arr) { int result = 0; int len = n / 2; for (int i = 1; i <= len; i++) { for (int j = i + 1; j <= len; j++) { result += map[arr[i]][arr[j]]; result += map[arr[j]][arr[i]]; } } return result; } void calculateAbility() { int *a = new int[n / 2 + 1]; int *b = new int[n / 2 + 1]; int ai = 1, bi = 1; for (int i = 1; i <= n; i++) { if (visit[i]) a[ai++] = i; else b[bi++] = i; } int abilityA = getAbility(a); int abilityB = getAbility(b); int result = abs(abilityA - abilityB); ans = min(ans, result); } void dfs(int v, int len) { if (n / 2 == len) { calculateAbility(); } else { for (int i = v + 1; i <= n; i++) { if (!visit[i]) { visit[i] = true; dfs(i, len + 1); } } } visit[v] = false; } int main(void) { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> map[i][j]; } } dfs(0, 0); cout << ans << endl; return 0; } |
오케이. 일단 다른 사람의 코드를 보고 이해를 하였습니다. 내가 짠 코드와 아이디어는 동일한데, 어디 부분에서 내가 틀린 것인지.... 내가 짠 코드의 한계는 무엇인지 살펴보도록 합니다. 그리고 배열 할당이 애매할 때는 동적할당은 구현해서 ,코드를 짜도록 합니다. 그리고 딜레트까지 해주면 좋습니다만, 안되도 가장 긴 배열까지만 형성이 되니, 이것은 신경쓰지 않도록 합니다. 백트리캥의 개념에 대해서 보면, dfs(pos+1, depth+1) 이것과 동일합니다. 동일하므로, 체크하지 않고 넘어가도록 하겠습니다. |
한가지 아쉬운점은 내가 코드를 구현할 때에도 가시적으로 20개중에 10개만 사용해도 된다는 것을 알았는데, 이것을 어떻게 적용할 수 있는 가입니다. 로또를 통해서 한번 찾아보도록 하겠습니다. |