소감 ¶
2005/02/19 Accepted 0:00.002 64
백트래킹문제. 따져줘야 하는 가지수가 적은 경우 최적화된 알고리즘을 찾는 것 보다는 그 가지수를 모두 따지는 것이 유리할 수도 있다.
백트래킹문제. 따져줘야 하는 가지수가 적은 경우 최적화된 알고리즘을 찾는 것 보다는 그 가지수를 모두 따지는 것이 유리할 수도 있다.
코드 ¶
~cpp // no10032 - Tug of War #include <iostream> #include <cstdlib> using namespace std; struct TugWar { int left; int right; }; const int MAX_CASE = 100; const int MAX = 100; inline void eatline() { while(cin.get() != '\n') continue; }; inline int comp(const void *i,const void *j) { return *(int *)i-*(int *)j; }; int main() { int nCase; int weight[MAX]; int left[MAX/2]; int right[MAX/2]; int nPeople; cin >> nCase; TugWar tugwar[MAX_CASE]; int i, j, k; int sumleft, sumright; int lcount, rcount; int tempSwap; for (i=0; i<nCase; i++) { eatline(); eatline(); cin >> nPeople; for (j=0; j<nPeople; j++) { cin >> weight[j]; } qsort(weight, nPeople, sizeof(int), comp); sumleft = sumright = 0; lcount = rcount = 0; for (j=nPeople-1; j>=0; j--) { if (sumleft <= sumright) { left[lcount++] = weight[j]; sumleft += weight[j]; if (j != 0) { right[rcount++] = weight[j-1]; sumright += weight[j-1]; j--; } } else { right[rcount++] = weight[j]; sumright += weight[j]; if (j != 0) { left[lcount++] = weight[j-1]; sumleft += weight[j-1]; j--; } } } int gap = sumleft - sumright; if (gap == 0) { tugwar[i].left = sumleft; tugwar[i].right = sumright; continue; } for (j=0; j<lcount; j++) { for (k=0; k<rcount; k++) { if (gap < 0) // 왼쪽편이 가벼울때 { if (abs(gap) > abs(abs(gap) - (2 * (right[k] - left[j])))) { sumleft += right[k] - left[j]; sumright -= right[k] - left[j]; tempSwap = left[j]; left[j] = right[k]; right[k] = tempSwap; gap = sumleft - sumright; break; } } else // 왼쪽편이 무거울때 { if (gap > abs(gap - (2 * (left[j] - right[k])))) { sumleft -= left[j] - right[k]; sumright += left[j] - right[k]; tempSwap = left[j]; left[j] = right[k]; right[k] = tempSwap; gap = sumleft - sumright; break; } } } } if (sumleft > sumright) { tempSwap = sumleft; sumleft = sumright; sumright = tempSwap; } tugwar[i].left = sumleft; tugwar[i].right = sumright; } for (i=0; i<nCase; i++) { cout << tugwar[i].left << " " << tugwar[i].right << endl; if (i != nCase - 1) cout << endl; } return 0; }