==== 소감 ====
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; 
}
}}}
----
[TugOfWar] [문보창]