imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:18Z

New page

==== 소감 ====
2005/02/19 Accepted 0:00.002 64
백트래킹문제. 따져줘야 하는 가지수가 적은 경우 최적화된 알고리즘을 찾는 것 보다는 그 가지수를 모두 따지는 것이 유리할 수도 있다.
==== 코드 ====
// 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]] [[문보창]]

TugOfWar/문보창 - Revision history

imported>Unknown at 05:28, 7 February 2021