설명
회사 야유회에서 줄다리기를 하기로 했다. 야유회에 참가한 사람들을 두 편으로 공평하게 나눈다. 모든 사람들이 둘 중 한 편에 참여해야 하며, 두 편의 사람 수는 한 명이 넘게 차이가 나면 안 된다. 그리고 양 편에 속한 사람들 체중의 총합 차를 최소한으로 줄여야 한다.
입력
첫번째 라인은 줄다리기에 참여하는 모든 사람의 수(n명)를 나타낸다. 다음에 사람의 수만큼 n개의 라인이 따라온다. n개의 라인은 순서대로 1번째 사람의 몸무게부터 n번째 사람의 몸무게를 나타낸다. 몸무게는 1~450 사이의 숫자여야 한다. 줄다리기의 참여자는 최대 100명까지(n<=100)이다.
출력
출력값은 한 줄로 표시하며 2개의 숫자만 있어야 한다. 2개의 숫자는 한 팀의 총 몸무게와 다른 한팀의 총 몸무게를 의미한다. 만약 두개의 숫자가 다를 경우 적은 숫자를 앞에 표시한다.
입력 예
3
100
90
200
출력 예
190 200
위와 같은 입출력을 처리 할 수 있는 프로그램을 작성하시오.
아래의 값으로 프로그램을 체크하시오
3
100
90
200
6
45
55
70
60
50
75
4
92
56
47
82
5
2
3
4
7
8
4
50
50
100
200
는 각각 다음과 같은 출력값이 나와야 함
190 200
175 180
138 139
12 12
150 250
57개의 풀이가 있습니다.
c 언어로 입력했어요.
#include <stdio.h>
int main(void)
{
int arr16[10000], ar1[10000], ar2[10000], arr3[10000], arr[10000], arr1[10000], arr2[10000], arr4[10000], arr5[10000], arr6[10000], arr7[10000], arr8[10000], arr9[10000], arr10[10000], arr11[10000], arr12[10000], arr13[10000], arr14[10000], arr15[10000];
int vvvv = 0, vvvvv = 0, kkkk = 0, rrrr = 0, cccc = 0, aaaa = 0, bbbb = 0, ee = 0, ww = 0, eeee = 0, ggg = 0, iii = 0, iiii = 0, lll = 0, rr = 0, tt = 0, dd = 0, kk = 0, ll = 0, yy = 0, zz = 0, xx = 0, xxx = 0, ccc = 0, ddd = 0, ttt = 0, rrr = 0, aa = 0, r = 0, t = 0, u = 0, bb = 0, eee = 0, gg = 0, hh = 0, ii = 0, p = 0, q = 0, jj = 0, a = 0, b = 0, c = 0, d = 0, e = 0, m = 0, f = 0, ff = 0, fff = 0, ffff = 0, g = 0, h = 0, i = 0, j = 0, k = 0, l = 0;
unsigned int cc = 0;
H:
G:
if(vvvv > 0)
{
printf("다시 처음 부터 입력하시요.\n");
}
printf("줄다리기를 할 두팀의 총 인원 수를 입력하시요. (1 ~ 100 명 사이. 다음 엔터).\n");
scanf("%d", &a);
if(a > 100 || a < 2)
{
vvvv++;
goto G;
}
for(b = 0; b < a; b++)
{
vvvvv++;
printf("%d 번째 사람의 몸무게를 입력하시요. (1 ~ 450 사이. 다음 엔터) : ", vvvvv);
scanf("%d", &arr[b]);
if(arr[b] > 450 || arr[b] < 1)
{
for(b = 0; b < a; b++)
{
arr[b] = 0;
}
vvvv++;
vvvvv = 0;
goto H;
}
}
for(b = 0; b < a; b++)
{
c = c + arr[b];
arr10[b] = arr[b];
}
c = (int) c/2;
for(b = 0; b < a - 1; b++)
{
for(d = 0; d < a - 1; d++)
{
if(arr[d] > arr[d + 1])
{
e = arr[d];
arr[d] = arr[d + 1];
arr[d + 1] = e;
}
}
}
for(d = 0; d < a - 1; d++)
{
arr16[d] = arr[d + 1] - arr[d];
}
for(b = 0; b < a - 1; b++)
{
for(d = 0; d < a - 1; d++)
{
if(arr16[d] > arr16[d + 1])
{
e = arr16[d];
arr16[d] = arr16[d + 1];
arr16[d + 1] = e;
}
}
}
i = arr16[0];
for(b = 0; b < a - 1; b++)
{
for(d = 0; d < a - 1; d++)
{
if(arr[d] < arr[d + 1])
{
e = arr[d];
arr[d] = arr[d + 1];
arr[d + 1] = e;
}
}
}
while(1)
{
if(gg <= hh)
{
arr4[aa] = arr[eee];
gg = gg + arr4[aa];
aa++;
}
else
{
arr5[bb] = arr[eee];
hh = hh + arr5[bb];
bb++;
}
eee++;
if(aa + bb > a - 1)
break;
}
yy = aa;
zz = bb;/*
aaaa = gg;
bbbb = hh;*/
if(gg > hh)
{
cc = hh;
dd = gg;
}
else if(gg < hh)
{
cc = gg;
dd = hh;
}
if(aa > bb)
{
for(b = 0; b < cc; b++)
{
if(aa > bb)
{
for(e = b; e < b + 1; e++)
{
gg = gg - arr4[e];
}
for(d = b; d < b + 1; d++)
{
hh = hh + arr4[d];
}
bb++;
aa--;
if(aa <= bb)
break;
}
}
}
else if(aa < bb)
{
for(b = 0; b < cc; b++)
{
for(e = b; e < b + 1; e++)
{
gg = gg + arr5[e];
}
for(d = b; d < b + 1; d++)
{
hh = hh - arr5[d];
}
bb--;
aa++;
if(aa >= bb)
break;
}
}
for(b = 0; b < a - 1; b++)
{
for(d = 0; d < a - 1; d++)
{
if(arr[d] > arr[d + 1])
{
e = arr[d];
arr[d] = arr[d + 1];
arr[d + 1] = e;
}
}
}
if(a==3)
{
while(1)
{
if(g <= h)
{
arr1[ff] = arr[fff];
g = g + arr1[ff];
ff++;
}
else
{
arr2[f] = arr[fff];
h = h + arr2[f];
f++;
}
fff++;
if(ff + f > a - 1)
break;
}
ggg = g;
lll = h;
if(ff > f && g > h)
{
g = g - arr[0];
h = h + arr[0];
}
else if(ff < f && g < h)
{
g = g + arr[1];
h = h - arr[1];
}
if(g > h)
{
if(ggg > lll)
{
if(ggg - lll < g - h)
{
g = ggg;
h = lll;
}
}
else
{
if(lll - ggg < g - h)
{
g = ggg;
h = lll;
}
}
}
else
{
if(ggg > lll)
{
if(ggg - lll < h - g)
{
g = ggg;
h = lll;
}
}
else
{
if(lll - ggg < h - g)
{
g = ggg;
h = lll;
}
}
}
}/*
gg = aaaa;
hh = bbbb;
if(gg > hh)
{
cc = gg;
dd = hh;
}
else if(gg < hh)
{
cc = hh;
dd = gg;
}
else
{
cc = gg - hh;
dd = gg;
}
arr12[0] = 0;*/
/*if(a > 5)
{
while(1)
{*/
if(a > 5 && a!=3)
{
while(1)
{
for(b = 0; b < a; b++)
{
ar1[b] = arr[a - 1 - b];
}
if(tt==a - 1 && rr==a - 1)
{
for(b = 0; b < a; b++)
{
if(tt==a - 1 && rr==a - 1)
{
arr[b] = ar1[b];
}
}
}
if(rr==a - 1)
{
rr = 0;
}
if(tt==a - 1)
{
tt = 0;
}
for(d = tt; d < a - 1; d++)
{
for(b = rr; b < a - 1; b++)
{
e = arr[b];
arr[b] = arr[b + 1];
arr[b + 1] = e;
}
break;
}
if(a!=3)
{
while(1)
{
if(fff%2==0)
{
arr1[ff] = arr[fff];
g = g + arr1[ff];
ii = g;
ff++;
}
else
{
arr2[f] = arr[fff];
h = h + arr2[f];
jj = h;
f++;
}
fff++;
if(ff + f > a - 1)
break;
}
if(a%2==1)
{
if(ff > f)
{
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
for(b = 0; b < ff; b++)
{
for(d = 0; d < ff; d++)
{
if(b!=f && d==f)
break;
if(b==ff - 1 && d==ff - 1)
{
break;
if(g > h)
{
if(ff > f)
{
g = g - arr1[b];
h = h + arr1[b];
arr2[b] = arr1[b];
arr1[b] = 0;
ff--;
f++;
break;
}
}
else if(h > g)
{
if(ff < f)
{
g = g + arr2[b];
h = h - arr2[b];
arr1[b] = arr2[b];
arr2[b] = 0;
ff++;
f--;
break;
}
}
if(g==h)
{
k++;
break;
}
}
g = g - arr1[b];
g = g + arr2[d];
h = h + arr1[b];
h = h - arr2[d];
e = arr1[b];
arr1[b] = arr2[d];
arr2[d] = e;
if(g > h)
{
if((int) cc/1000000>=g - h)
{
k++;
break;
}
else
{
cc++;
if((int) cc/1000000 > dd)
{
cc = 0;
}
}
}
else if(h > g)
{
if((int) cc/1000000>=h - g)
{
k++;
break;
}
else
{
cc++;
if((int) cc/1000000 > dd)
{
cc = 0;
}
}
}
if(h==g)
{
k++;
break;
}
}
if(k==1)
break;
}
if(k==1)
break;
l = g;
m = h;
if(ff > f)
{
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
if(l - m > 0)
{
if(i >= l - m)
{
k++;
g = l;
h = m;
break;
}
}
else if(m - l > 0)
{
if(i >= m - l)
{
k++;
g = l;
h = m;
break;
}
}
}
}
else if(f > ff)
{
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
for(b = 0; b < f; b++)
{
for(d = 0; d < f; d++)
{
if(b!=ff && d==ff)
break;
if(b==f - 1 && d==f - 1)
{
break;
if(g > h)
{
if(ff > f)
{
g = g - arr1[b];
h = h + arr1[b];
arr2[b] = arr1[b];
arr1[b] = 0;
ff--;
f++;
break;
}
}
else if(h > g)
{
if(ff < f)
{
g = g + arr2[b];
h = h - arr2[b];
arr1[b] = arr2[b];
arr2[b] = 0;
ff++;
f--;
break;
}
}
if(g==h)
{
k++;
break;
}
}
g = g - arr1[b];
g = g + arr2[d];
h = h + arr1[b];
h = h - arr2[d];
e = arr1[b];
arr1[b] = arr2[d];
arr2[d] = e;
if(g > h)
{
if((int) cc/1000000>=g - h)
{
k++;
break;
}
else
{
cc++;
if((int) cc/1000000 > dd)
{
cc = 0;
}
}
}
else if(h > g)
{
if((int) cc/1000000>=h - g)
{
k++;
break;
}
else
{
cc++;
if((int) cc/1000000 > dd)
{
cc = 0;
}
}
}
if(g==h)
{
k++;
break;
}
}
if(k==1)
break;
}
if(k==1)
break;
l = g;
m = h;
if(ff < f)
{
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
if(l - m > 0)
{
if(i >= l - m)
{
k++;
g = l;
h = m;
break;
}
}
else if(m - l > 0)
{
if(i >= m - l)
{
k++;
g = l;
h = m;
break;
}
}
}
}
}
else
{
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
for(b = 0; b < ff; b++)
{
for(d = 0; d < f; d++)
{
g = g - arr1[b];
g = g + arr2[d];
h = h + arr1[b];
h = h - arr2[d];
e = arr1[b];
arr1[b] = arr2[d];
arr2[d] = e;
if(g > h)
{
if((int) cc/1000000>=g - h)
{
k++;
break;
}
else
{
cc++;
if((int) cc/1000000 > dd)
{
cc = 0;
}
}
}
else if(h > g)
{
if((int) cc/1000000>=h - g)
{
k++;
break;
}
else
{
cc++;
if((int) cc/1000000> dd)
{
cc = 0;
}
}
}
if(g==h)
{
k++;
break;
}
if(g > h)
{
if(i >= g - h)
{
k++;
break;
}
}
else
{
if(i >= h - g)
{
k++;
break;
}
}
}
if(k==1)
break;
}
if(k==1)
break;
}
}
ee = g;
ww = h;
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
if(g > h)
{
g = g - arr1[0];
h = h + arr1[0];
g = g + arr2[0];
h = h - arr2[0];
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
}
else if(g < h)
{
g = g - arr1[0];
h = h + arr1[0];
g = g + arr2[0];
h = h - arr2[0];
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
}
if(g > h)
{
if(ee > ww)
{
if(g - h > ee - ww)
{
g = ee;
h = ww;
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
rrrr++;
}
}
else if(ee < ww)
{
if(g - h > ww - ee)
{
g = ee;
h = ww;
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
rrrr++;
}
}
}
else if(g < h)
{
if(ee > ww)
{
if(h - g > ee - ww)
{
g = ee;
h = ww;
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
rrrr++;
}
}
if(ee < ww)
{
if(h - g > ww - ee)
{
g = ee;
h = ww;
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
rrrr++;
}
}
}
if(k==1)
break;
if(ff > f)
{
arr1[ff - 1] = 0;
}
else if(ff < f)
{
arr2[f - 1] = 0;
}
f = 0;
ff = 0;
fff = 0;
g = 0;
h = 0;
tt++;
rr++;
}
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
ee = g;
ww = h;
if(g > h)
{
g = g - arr1[0];
h = h + arr1[0];
g = g + arr2[0];
h = h - arr2[0];
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
}
else if(g < h)
{
g = g - arr1[0];
h = h + arr1[0];
g = g + arr2[0];
h = h - arr2[0];
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
}
if(g > h)
{
if(ee > ww)
{
if(g - h > ee - ww)
{
g = ee;
h = ww;
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
rrrr++;
}
}
else if(ee < ww)
{
if(g - h > ww - ee)
{
g = ee;
h = ww;
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
rrrr++;
}
}
}
else if(g < h)
{
if(ee > ww)
{
if(h - g > ee - ww)
{
g = ee;
h = ww;
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
rrrr++;
}
}
if(ee < ww)
{
if(h - g > ww - ee)
{
g = ee;
h = ww;
e = arr1[0];
arr1[0] = arr2[0];
arr2[0] = e;
rrrr++;
}
}
}
}
/*if(g > h)
{
aaaa = g - h;
}
else if(g < h)
{
aaaa = h - g;
}
for(b = 0; b < ff; b++)
{
arr10[b] = arr1[b];
}
for(b = 0; b < f; b++)
{
arr11[b] = arr2[b];
}
arr13[cccc] = g;
arr14[cccc] = h;
if(aaaa==arr12[0])
break;
if(g > h)
{
cc = g - h - 1;
}
else if(h > g)
{
cc = h - g - 1;
}
if(g > h)
{
arr12[cccc] = g - h;
cccc++;
}
else if(g < h)
{
arr12[cccc] = h - g;
cccc++;
}
for(b = 0; b < cccc; b++)
{
if(arr12[b] > arr12[b + 1])
{
e = arr12[b];
arr12[b] = arr12[b + 1];
arr12[b + 1] = e;
e = arr13[b];
arr13[b] = arr13[b + 1];
arr13[b + 1] = e;
e = arr14[b];
arr14[b] = arr14[b + 1];
arr14[b + 1] = e;
}
}
aaaa = 0, bbbb = 0, ee = 0, ww = 0, eeee = 0, ggg = 0, iii = 0, iiii = 0, lll = 0, rr = 0, tt = 0, dd = 0, kk = 0, ll = 0, yy = 0, zz = 0, xx = 0, xxx = 0, ccc = 0, ddd = 0, ttt = 0, rrr = 0, aa = 0, r = 0, t = 0, u = 0, bb = 0, cc = 0, eee = 0, gg = 0, hh = 0, ii = 0, p = 0, q = 0, jj = 0, a = 0, b = 0, c = 0, d = 0, e = 0, m = 0, f = 0, ff = 0, fff = 0, ffff = 0, g = 0, h = 0, i = 0, j = 0, k = 0, l = 0;
}
g = arr13[cccc];
h = arr14[cccc];
for(b = 0; b < ff; b++)
{
arr1[b] = arr10[b];
}
for(b = 0; b < f; b++)
{
arr2[b] = arr11[b];
}
a = 1000;
}*/
if(a!=3 && a < 6)
{
while(1)
{
for(b = 0; b < a; b++)
{
ar1[b] = arr[a - b - 1];
}
if(tt==a - 1 && rr==a - 1)
{
for(b = 0; b < a; b++)
{
if(tt==a - 1 && rr==a - 1)
{
arr[b] = ar1[b];
}
}
}
if(rr==a - 1)
{
rr = 0;
}
if(tt==a - 1)
{
tt = 0;
}
for(d = tt; d < a - 1; d++)
{
for(b = rr; b < a - 1; b++)
{
e = arr[b];
arr[b] = arr[b + 1];
arr[b + 1] = e;
}
break;
}
if(a!=3)
{
while(1)
{
if(fff%2==0)
{
arr1[ff] = arr[fff];
g = g + arr1[ff];
ii = g;
ff++;
}
else
{
arr2[f] = arr[fff];
h = h + arr2[f];
jj = h;
f++;
}
fff++;
if(ff + f > a - 1)
break;
}
if(a%2==1)
{
if(ff > f)
{
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
for(b = 0; b < ff; b++)
{
for(d = 0; d < ff; d++)
{
if(b!=ff - 1 && d==ff - 1)
break;
if(b==ff - 1 && d==ff - 1)
{
if(g > h)
{
if(ff > f)
{
g = g - arr1[b];
h = h + arr1[b];
arr2[b] = arr1[b];
arr1[b] = 0;
ff--;
f++;
break;
}
else
{
break;
}
}
else if(h > g)
{
if(ff < f)
{
g = g + arr2[b];
h = h - arr2[b];
arr1[b] = arr2[b];
arr2[b] = 0;
ff++;
f--;
break;
}
else
{
break;
}
}
if(h==g)
{
k++;
break;
}
}
g = g - arr1[b];
g = g + arr2[d];
h = h + arr1[b];
h = h - arr2[d];
e = arr1[b];
arr1[b] = arr2[d];
arr2[d] = e;
if(g > h)
{
if((int) cc/100>=g - h)
{
k++;
break;
}
else
{
cc++;
if((int) cc/100 > dd)
{
cc = 0;
}
}
}
else if(h > g)
{
if((int) cc/100>=h - g)
{
k++;
break;
}
else
{
cc++;
if((int) cc/100 > dd)
{
cc = 0;
}
}
}
if(h==g)
{
k++;
break;
}
}
if(k==1)
break;
}
l = g;
m = h;
if(ff > f)
{
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
if(l - m > 0)
{
if(i >= l - m)
{
k++;
g = l;
h = m;
break;
}
}
else if(m - l > 0)
{
if(i >= m - l)
{
k++;
g = l;
h = m;
break;
}
}
}
}
else if(f > ff)
{
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
for(b = 0; b < f; b++)
{
for(d = 0; d < f; d++)
{
if(b!=ff - 1 && d==ff - 1)
break;
if(b==f - 1 && d==f - 1)
{
if(g > h)
{
if(ff > f)
{
g = g - arr1[b];
h = h + arr1[b];
arr2[b] = arr1[b];
arr1[b] = 0;
ff--;
f++;
break;
}
else
{
break;
}
}
else if(h > g)
{
if(ff < f)
{
g = g + arr2[b];
h = h - arr2[b];
arr1[b] = arr2[b];
arr2[b] = 0;
ff++;
f--;
break;
}
else
{
break;
}
}
if(h==g)
{
k++;
break;
}
}
g = g - arr1[b];
g = g + arr2[d];
h = h + arr1[b];
h = h - arr2[d];
e = arr1[b];
arr1[b] = arr2[d];
arr2[d] = e;
if(g > h)
{
if((int) cc/100>=g - h)
{
k++;
break;
}
else
{
cc++;
if((int) cc/100 > dd)
{
cc = 0;
}
}
}
else if(h > g)
{
if((int) cc/100>=h - g)
{
k++;
break;
}
else
{
cc++;
if((int) cc/100 > dd)
{
cc = 0;
}
}
}
if(g==h)
{
k++;
break;
}
}
if(k==1)
break;
}
l = g;
m = h;
if(ff < f)
{
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
if(l - m > 0)
{
if(i >= l - m)
{
k++;
g = l;
h = m;
break;
}
}
else if(m - l > 0)
{
if(i >= m - l)
{
k++;
g = l;
h = m;
break;
}
}
}
}
}
else
{
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
for(b = 0; b < ff; b++)
{
for(d = 0; d < f; d++)
{
g = g - arr1[b];
g = g + arr2[d];
h = h + arr1[b];
h = h - arr2[d];
e = arr1[b];
arr1[b] = arr2[d];
arr2[d] = e;
if(g > h)
{
if((int) cc/100>=g - h)
{
k++;
break;
}
else
{
cc++;
if((int) cc/100 > dd)
{
cc = 0;
}
}
}
else if(h > g)
{
if((int) cc/100>=h - g)
{
k++;
break;
}
else
{
cc++;
if((int) cc/100 > dd)
{
cc = 0;
}
}
}
if(g==h)
{
k++;
break;
}
if(g > h)
{
if(i >= g - h)
{
k++;
break;
}
}
else
{
if(i >= h - g)
{
k++;
break;
}
}
}
if(k==1)
break;
}
}
}
if(k==1)
break;
if(ff > f)
{
arr1[ff - 1] = 0;
}
else if(ff < f)
{
arr2[f - 1] = 0;
}
f = 0;
ff = 0;
fff = 0;
g = 0;
h = 0;
tt++;
rr++;
i++;
}
for(b = 0; b < ff - 1; b++)
{
if(arr1[b] > arr1[b + 1])
{
e = arr1[b];
arr1[b] = arr1[b + 1];
arr1[b + 1] = e;
}
}
for(b = 0; b < f - 1; b++)
{
if(arr2[b] > arr2[b + 1])
{
e = arr2[b];
arr2[b] = arr2[b + 1];
arr2[b + 1] = e;
}
}
}
gg = 0;
hh = 0;
for(b = 0; b < ff - 1; b++)
{
for(d = 0; d < ff - 1; d++)
{
if(arr1[d] > arr1[d + 1])
{
e = arr1[d];
arr1[d] = arr1[d + 1];
arr1[d + 1] = e;
}
}
}
for(b = 0; b < f - 1; b++)
{
for(d = 0; d < f - 1; d++)
{
if(arr2[d] > arr2[d + 1])
{
e = arr2[d];
arr2[d] = arr2[d + 1];
arr2[d + 1] = e;
}
}
}
if(h > g)
{
printf("%d %d\n\n", g, h);
}
else
{
printf("%d %d\n\n", h, g);
}
return 0;
}
Python3
가장먼저 할일은 팀원을 배정받은 후에 팀인원이 홀수인 경우 몸무게가 0인 가상의 팀원을 하나 배열에 추가하여 짝이 맞도록 한다. 우선 팀원중 아무나 한명을 선발하고 남아있는 팀원들중 몸무게 차이가 가장 적게나는 사람을 선발한다. 둘의 몸무게를 비교하여 몸무게가 많이 나가는 사람을 현재까지 몸무게 총합이 적은팀으로 보내고 몸무게가 적게 나가는 사람을 현재까지 몸무게 총합이 큰팀으로 보내어 균형을 맞춘다. 남아있는 사람이 없을때 까지 이것을 반복한다. 즉 각 개인의 몸무게 차이가 가장 적은 사람들끼리 팀을 나누면 결과적으로 팀간의 몸무게차가 최소가 되는 원리이다.
def balance(weights, left, right):
weight = weights.pop()
# find closed number with weight
closedValue = min([(999, 0)] + [(abs(weight-x), x) for x in weights])[1]
weights.remove(closedValue)
if left > right:
left += min(weight, closedValue)
right += max(weight, closedValue)
else:
left += max(weight, closedValue)
right += min(weight, closedValue)
if len(weights) != 0:
return balance(weights, left, right)
return (left, right) if left < right else (right, left)
while True:
# input count and weights
count = int(input("Input Count : "))
array = []
for x in range(count):
array.append(max(1, min(450, int(input("%d. Input weight : " % (x+1))))))
# make even length
if len(array) % 2 == 1:
array.append(0)
# show result
print("Result : %d %d\n" % balance(array, 0, 0))
결과
Input Count : 3
1. Input weight : 100
2. Input weight : 90
3. Input weight : 200
Result : 190 200
Input Count : 6
1. Input weight : 45
2. Input weight : 55
3. Input weight : 70
4. Input weight : 60
5. Input weight : 50
6. Input weight : 75
Result : 175 180
Input Count : 4
1. Input weight : 92
2. Input weight : 56
3. Input weight : 47
4. Input weight : 82
Result : 138 139
Input Count : 5
1. Input weight : 2
2. Input weight : 3
3. Input weight : 4
4. Input weight : 7
5. Input weight : 8
Result : 12 12
Input Count : 4
1. Input weight : 50
2. Input weight : 50
3. Input weight : 100
4. Input weight : 200
Result : 150 250
Sub Main()
Dim cnt As Integer = Val(Console.ReadLine)
Dim arr As New List(Of Integer)
For i As Integer = 1 To cnt
arr.Add(Val(Console.ReadLine))
Next
Dim b As Integer = arr.Sum / 2 '// 조합 최소값에 근접하게 구함
Dim lastD As Integer = arr.Sum, result As Integer = 0
Dim tArr() As String = Permutation.Create(String.Join("", Enumerable.Range(1, cnt)).ToArray, False).ToArray
For i As Integer = 0 To tArr.Length - 1
For k As Integer = -1 To 1
Dim t As String = tArr(i).Substring(0, tArr(i).Length / 2)
Dim s As Integer = 0
For j As Integer = 0 To t.Length - 1
s += arr(t.Substring(j, 1) - 1)
Next
If lastD > Math.Abs(b - s) Then
lastD = Math.Abs(b - s)
result = s
End If
Next
Next
Dim results() As Integer = {arr.Sum - result, result}
Console.WriteLine("{0} {1}", results.Min, results.Max)
Console.ReadLine()
End Sub
python3입니다. 임의로 두 개의 그룹으로 나눈다음, 한 멤버씩 swap해가면서 차이가 가장 적게 나는 편성을 탐색했습니다.
def sol(tc):
sz = int((len(tc) + 1) / 2)
a, b = tc[0:sz], tc[sz:len(tc)]
diff = abs(sum(a) - sum(b))
sola, solb = a[:], b[:]
for i in range(0, len(a)):
for j in range(0, len(b)):
ta, tb = a[:], b[:]
tb.append(ta.pop(i))
ta.append(tb.pop(j))
td = abs(sum(ta) - sum(tb))
if td < diff:
diff = td
sola, solb = ta[:], tb[:]
if (sum(sola) > sum(solb)): sola, solb = solb, sola
return (sum(sola), sum(solb))
for tc in [[100, 90, 200], [45, 55, 70, 60, 50, 75], [92,56, 47, 82], [2, 3, 4, 7, 8], [50, 50, 100, 200]]:
(a, b) = sol(tc)
print("%d %d" % (a, b))
import java.util.Scanner;
public class Calculate {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("참가인원수 입력 : ");
int n = s.nextInt();
int [] a = new int [n/2]; // 참가인원수를 반으로 나눠 배열 생성
int [] b = new int [n/2+n%2]; // 참가인원이 홀수일때는 b배열에 1 추가
for(int i=0 ; i<n ; i++){
System.out.println((i+1)+"번째 인원 몸무게 입력 :");
if (i < n/2) a[i] = s.nextInt();
else b[i-n/2] = s.nextInt();
}
int totalA = sum(a); //최초 합계 계산
int totalB = sum(b); //최초 합계 계산
int tmp = 0;
for(int j=0 ; j<a.length ; j++){
for(int k=0 ; k<b.length ; k++){
if(Math.abs(totalA-totalB) > Math.abs( (totalA-a[j]+b[k]) - (totalB-b[k]+a[j]) )){
// 임시적으로 값을 교환해 계산한 결과가 교환전 결과보다 차이가 적을 때 실제 값 변경
tmp = a[j];
a[j] = b[k];
b[k] = tmp;
totalA = sum(a); // 치환 후 합계 계산
totalB = sum(b);
}
}
}
if (totalA > totalB ) System.out.println(totalB + " " + totalA );
else System.out.println(totalA + " " + totalB );
}
public static int sum(int[] list) {
int total = 0;
for(int i=0 ; i<list.length ; i++)
total +=list[i];
return total;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr= new int[n];
int SUM=0;
//예를 들어 arr배열에는 2,2,7,8,3,2가 들어갔다고 가정하자
for(int i=0; i<arr.length; i++) {arr[i]=sc.nextInt(); SUM+=arr[i];}
int SUMh = SUM/2;
sc.close();
//arr을 내림차순으로 정렬 -> 8,7,3,2,2,2
for(int i=0; i<arr.length; i++) {
for(int j=i; j<arr.length; j++) {
if(arr[j]>arr[i]) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
int[] team1 = new int[n/2];
int sum=0;
//team1배열에는 8,7,3이 들어가게 된다
for(int i=0; i<team1.length; i++) {team1[i]=arr[i]; sum+=team1[i];}
//sum값은 최대한 SUM/2가 되어야 한다
//SUM-sum을 diff로 정의
int diff = Math.abs(SUMh - sum);
//diff는 이상적인 팀 무게(SUMh) 와 초기 팀무게(sum)의 차이
int sumNew=0;
//team1[j]위치 값보다 arr[i]에 작은 값이 있는지 찾아본다
//team1[j]위치 값보다 작은값을 찾을 수 없다면
//team1[j-1]의 값보다 arr[i]에 작은값이 있는지 찾아본다
//sumNew값이 들어갈 배열 생성
int[] sumarr = new int[team1.length*arr.length];
for(int j=team1.length-1,s=0; j>=0; j--) {
for(int i=0; i<arr.length; i++) {
if(team1[j]>arr[i]) {
int tmp = team1[j];
team1[j]=arr[i];
sumNew = sum - tmp + team1[j];
sum = sumNew;
sumarr[s] = sumNew;
s++;
}
}
}
int min = sumarr[0];
for(int i=0; i<sumarr.length; i++) {
if(min>sumarr[i] && sumarr[i]>=SUMh) {
min=sumarr[i];
}
}
int left = min;
int right = SUM-min;
System.out.println(left + ", " + right);
}
def bal_dv(weight):
if len(weight)%2: weight.append(0)
weight.sort()
balwg = sum(weight)/2
x = [[],[]]
for i in range(len(weight)):
x[i%2].append(weight[i])
x[0][-1],x[1][-1] = x[1][-1],x[0][-1]
while 1:
dv = balwg - sum(x[0])
if dv == 0: return x
diff = []
for i in range(len(x[0])-1):
for j in range(len(x[1])-1):
diff.append(x[1][j] - x[0][i])
tmp = [abs(dv-i) for i in diff]
if tmp[tmp.index(min(tmp))] >= abs(dv): return x
x0i = int(tmp.index(min(tmp))//(len(diff)**0.5))
x1i = int(tmp.index(min(tmp))%(len(diff)**0.5))
x[0][x0i],x[1][x1i] = x[1][x1i],x[0][x0i]
if min(tmp) == 0: return x
weight = [[100, 90, 200],[45,55,70,60,50,75],[92,56,47,82],[2,3,4,7,8],[50,50,100,200],[1,3,4,7,9],[1,2,3,7,9],[1,2,4,7,8],[10,4,3,2,1],[1,2,3,4,5,100]]
for i in range(len(weight)):
b = bal_dv(weight[i])
print('case{}: {}\n{} : {} ----- {} : {}\n'.format(i+1, weight[i],sum(b[0]),sum(b[1]),b[0],b[1]))
결과
case1: [0, 90, 100, 200]
200 : 190 ----- [0, 200] : [90, 100]
case2: [45, 50, 55, 60, 70, 75]
175 : 180 ----- [45, 55, 75] : [50, 60, 70]
case3: [47, 56, 82, 92]
139 : 138 ----- [47, 92] : [56, 82]
case4: [0, 2, 3, 4, 7, 8]
12 : 12 ----- [0, 4, 8] : [2, 3, 7]
case5: [50, 50, 100, 200]
250 : 150 ----- [50, 200] : [50, 100]
case6: [0, 1, 3, 4, 7, 9]
12 : 12 ----- [0, 3, 9] : [1, 4, 7]
case7: [0, 1, 2, 3, 7, 9]
11 : 11 ----- [0, 2, 9] : [1, 3, 7]
case8: [0, 1, 2, 4, 7, 8]
11 : 11 ----- [1, 2, 8] : [0, 4, 7]
case9: [0, 1, 2, 3, 4, 10]
11 : 9 ----- [0, 1, 10] : [2, 3, 4]
case10: [1, 2, 3, 4, 5, 100]
103 : 12 ----- [1, 2, 100] : [3, 4, 5]
경우의 수가 너무 많아서 모든 경우의 수를 체크하는 것은 포기하고, 다른 방식을 모색했습니다
처음에는 가장 큰 수, 그 다음 큰수 로 나눈 뒤, 둘의 차이를 최소화하는 수를 분배하는 방식...
윗수부터 분배 아랫수부터 분배 등등을 고려했지만
자잘하게 분리가 안 되는 케이스가 발생하더군요
최종적으로는
가장 큰 수, 그 다음 큰 수...2개의 집합에 작은 수부터 교대로 분배 한 후
2 집합의 원소들 중 스왑했을때 가장 이상적인 밸런스 값에 도달하는 원소들을 스왑하고
이 과정을 이상적인 밸런스 값에 수렴하거나 더 이상 줄이지 못할때까지 반복합니다
이게 맞는 풀이인지는 모르겠으나
극단적인 상황에서 오류를 뿜었던 몇몇 케이스에서도 제대로 작동되네요
우선 n//2명으로 구성할 수 있는 모든 경우의 수를 구합니다.
각 경우에 대해 그들의 몸무게 합과 전체 몸무게 합의 절반의 차이를 구합니다.
그 값이 가장 적은 값을 출력하면 됩니다.
from itertools import combinations
def TugWar(n, *args):
k = n//2
s = sum(args)/2 #전체 몸무게 합의 절반
combs = combinations(args, k) #k명으로 구성할 수 있는 모든 경우의 수
diff = list(map(lambda x : abs(s - sum(x)), combs)) #k명의 몸무게 합과 전체 몸무게의 절반과의 차이
return [int(s - min(diff)), int(s + min(diff))] #차이가 최소가 되는 부분을 출력
print(TugWar(6, 45, 55, 70, 60, 50, 75))
Clojure 코드입니다.
주어진 수들 중의 절반 (또는 절반-1개)를 조합해서 그 합계값이 (총합 / 2) 와 가장 근접한 조합을 찾도록 했습니다.
(use 'clojure.math.combinatorics)
(defn calc
[coll]
(let [abs #(if (neg? %) (- %) %)
sum (reduce + coll)
half-sum (/ sum 2)
size (count coll)
combos (into (combinations coll (quot size 2))
(if (even? size)
nil
(combinations coll (inc (quot size 2)))))
sums (map #(reduce + %) combos)
differences (map #(abs (- % half-sum)) sums)
mini (apply min differences)]
(format "%s %s" (- sum (+ mini half-sum)) (+ mini half-sum))))
(defn parse
[s]
(let [lines (filter (complement empty?) (clojure.string/split-lines s))
numbers (map #(Integer/parseInt %) lines)]
(loop [left (first numbers)
numbers numbers
n-acc []
coll-acc []]
(cond (empty? numbers) coll-acc
(zero? left) (recur (second numbers)
(rest numbers)
[]
(conj coll-acc n-acc))
true (recur (dec left)
(rest numbers)
(conj n-acc (second numbers))
coll-acc)))))
(defn tug-of-war
[s]
(let [queries (parse s)
answers (map calc queries)]
(doseq [a answers]
(println a))))
어휴 어렵네요 ㅋㅋㅋㅋ! 저도 윗분처럼 사람들중 절반(사람수가 홀수이면 절반-1)의 몸무게 합이 총합/2에 근접한 값을 찾도록 했는데요. 조합할 몸무게값의 배열주소를 가지는 또다른 주소배열(juso[n/2])을 생성해서, 조합할 값이 총합/2에 근접할 때까지 그 주소배열의 조합이 변하도록 만들어내는데 시간이 걸렸어요 ㅋㅋ 어휴.. Java로 만들었습니당 ㅎㅎ
package h17_tug_of_war;
import java.util.Scanner;
public class Tug_of_war {
public static void main(String[] args) {
int n, nh, i, j, sum, half, team, diff;
Scanner in=new Scanner(System.in);
n=in.nextInt(); nh=n/2;
int[] arr=new int[n];
for(i=0, sum=0;i<n;i++){
arr[i]=in.nextInt();
sum+=arr[i];
} //여기까진 입력을 받음
half=sum/2; diff=half;
int[] juso=new int[nh]; //연산 중 arr배열을 다루기 위한 주소 juso배열 생성
for(i=0;i<nh;i++) juso[i]=i; //juso 초기화
int[] opt_juso=new int[nh]; //결과값 주소를 담을 opt_juso
finding_opt:
while(juso[0]<=(n-nh)){
team=0;// 임시 team의 총합 구한뒤 team-half의 절대값이 임시diff값보다 작을 경우 opt_juso교체
for(i=0;i<nh;i++) team+=arr[juso[i]];
if(diff>((team>half)? team-half:half-team)){
diff=((team>half)? team-half:half-team);
for(i=0;i<nh;i++) opt_juso[i]=juso[i];
}
for(j=1;juso[nh-j]==(n-j);j++){ if(j==nh) break finding_opt; }
juso[nh-j]++;//juso가 각각이 가리킬 수 있는 마지막배열을 가리키지 않는 주소 찾기,juso변화시킴
for(--j;j>0;j--) juso[nh-j]=juso[nh-j-1]+1;//주소의 끝이 arr의 끝에 도달했을 때 주소재배열
}
team=0; //구한 opt_juso로 half에 가장 근접하는 team 몸무게합 구하기
for(i=0;i<nh;i++) team+=arr[opt_juso[i]];
team=(team<=half)? team: (sum-team);
System.out.println(team+" "+(sum-team));
}
}
tug.war=function(txt){
txta=as.list(unlist(strsplit(txt, "\n\n")))
txta=sapply(txta, function(a) strsplit(a, "\n", ""))
txta=sapply(txta, as.integer)
tug = function(v){
length=v[1]
data=v[-1]
weight.team1=apply(combn(data, length%/%2), 2, sum)
weight.team2=rep(sum(data), length(weight.team1))-weight.team1
m=which.min(abs(weight.team1-weight.team2))
print(paste(weight.team1[m], weight.team2[m]))
}
sapply(txta, tug)
on.exit()
}
받은 내용을 줄 별로 나누고 숫자로 변환했습니다. 그리고 첫 값을 길이, 나머지를 데이터로 받고 전체 팀원에서 길이를 2로 나눈 몫의 수만큼 사람을 선택하는 조합을 내장 조합 함수를 이용해서 계산한다음, (선택되지 않은 팀의 몸무게 총합) = (전체 몸무게 총합) - (선택된 팀의 몸무게 총합)이라는 점에 착안하여 두 팀간의 몸무게 절대값의 차이가 가장 작은 경우를 출력했습니다. 아래는 결과화면입니다.
sample="3
100
90
200
6
45
55
70
60
50
75
4
92
56
47
82
5
2
3
4
7
8
4
50
50
100
200"
> tug.war(sample)
[1] "200 190"
[1] "175 180"
[1] "139 138"
[1] "12 12"
[1] "150 250"
조합으로 N/2명을 뽑아내려 하면 최대 10C5 = 100891344545564193334812497256이 됩니다. 이러면 경우의 수가 너무 늘어나서 도저히 다 체크할 방법이 없죠.
무게를 기준으로 상태를 나타내면 사람의 몸무게는 0~450이므로 100명의 몸무게를 아무리 조합해봐야 0~45000 사이에 있게 됩니다. Dynamic Programming의 점화식으로 나타내면
isPossible[i][j][k] = i번째 사람까지만 고려했을 때, 그 중 j명을 뽑아 몸무게 합이 k가 되도록 할 수 있는가? 정도로 표현되겠네요. 전체 상태의 수는 많아야 100 x 100 x 45000이므로 100,891,344,545,564,193,334,812,497,256 개에 비하면 고려해야 할 상태의 수가 약 224,202,987,879,031,540,744분의 1 정도로 줄어들었습니다. 아무리 오래 잡아도 1초 이내에는 답을 구할 수 있습니다.
코드에서 PossibleWeights[m] = 사람을 m명 뽑아서 만들 수 있는 몸무게의 합들의 집합입니다.
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
const int maxPeopleCnt = 100;
set<int> PossibleWeights[maxPeopleCnt];
inline int abs(int n){
return n < 0? -n: n;
}
int main(){
int n;
scanf("%d",&n);
vector<int> weights(n);
int weight_sum = 0;
for(int i = 0; i < n; ++i){
scanf("%d", &weights[i]);
weight_sum += weights[i];
}
set<int>::iterator it;
PossibleWeights[0].insert(0);
for(int peopleIndex = 0 ; peopleIndex < n; peopleIndex++){
for(int peopleCnt = peopleIndex; peopleCnt >=0; --peopleCnt){
for( it = PossibleWeights[peopleCnt].begin(); it != PossibleWeights[peopleCnt].end(); it++){
PossibleWeights[peopleCnt+1].insert((*it) + weights[peopleIndex]);
}
}
}
int objective = weight_sum / 2;
int answer = -1;
for(it = PossibleWeights[n / 2].begin(); it != PossibleWeights[n / 2].end(); it++){
if( abs(objective - answer) < abs(objective - *it) ) continue;
answer = *it;
}
int answer_2 = weight_sum - answer;
if(answer_2 < answer) swap(answer, answer_2);
printf("%d %d\n", answer, answer_2);
return 0;
}
제가 생각한 알고리즘은 단순합니다.
파이썬입니다.
import unittest
import random
class TugOfWar:
def __init__(self, a, b):
#
# a: a-team, b: b-team
#
self.a = a
self.b = b
def change(self, a_index, b_index):
#
# change each other
#
self.a[a_index], self.b[b_index] = self.b[b_index], self.a[a_index]
def sum_a(self):
return sum(self.a)
def sum_b(self):
return sum(self.b)
def next(self):
a_sum = self.sum_a()
b_sum = self.sum_b()
current_gap = abs(a_sum-b_sum)
min_gap = 450 * len(self.a)
found = False
for i, member_a in enumerate(self.a):
for j, member_b in enumerate(self.b):
#
# change member_a(100, 50) to member_b(50, 100)
#
gap = member_a-member_b # 50, -50
next_a_sum = a_sum-gap
next_b_sum = b_sum+gap
next_gap = abs(next_a_sum - next_b_sum)
if next_gap < current_gap and next_gap < min_gap:
min_gap = next_gap
found = True
a_index = i
b_index = j
if found: return (a_index, b_index)
def balance(self):
while True:
found_index = self.next()
if found_index:
a_index, b_index = found_index
self.change(a_index, b_index)
else:
break
def makeTeam(src):
t = map(int, src.split())
half = len(t)/2
a, b = t[:half], t[half:]
tugOfWar = TugOfWar(a, b)
tugOfWar.balance()
result = []
result.append('[%s]' % src)
result.append('%s %s' % (tugOfWar.sum_a(), tugOfWar.sum_b()))
print '\n'.join(result)
#
# Test Code
#
class TugOfWarTest(unittest.TestCase):
def testChange(self):
tow = TugOfWar([1,2,3], [4,5,6])
tow.change(0,0)
self.assertEquals([4,2,3], tow.a)
self.assertEquals([1,5,6], tow.b)
def testSum(self):
tow = TugOfWar([1,2,3], [4,5,6])
self.assertEquals(6, tow.sum_a())
self.assertEquals(15, tow.sum_b())
def testOptimalBalance(self):
tow = TugOfWar([1,2,3], [4,5,6])
self.assertEquals((0,1), tow.next())
def testMakeBalance(self):
tow = TugOfWar([1,2,3], [4,5,6])
tow.balance()
self.assertEquals([5,2,3], tow.a)
self.assertEquals([4,1,6], tow.b)
def testMakeTeam(self):
makeTeam("1 2 3 4 5 6")
makeTeam("100 90 200")
makeTeam("45 55 70 60 50 75")
makeTeam("92 56 47 82")
makeTeam("2 3 4 7 8")
makeTeam("50 50 100 200")
case_100 = ' '.join([str(random.randint(1, 450)) for i in range(100)])
makeTeam(case_100)
if __name__ == "__main__":
unittest.main()
C입니다.
#include <stdio.h>
int arrsum(int *a, int alen)
{
int i;
int result=0;
for(i=0;i<alen;i++) result = result+a[i];
return result;
}
int abs(int a)
{
if(a>=0) return a;
return -a;
}
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void tug(int *a, int *b, int alen, int blen)
{
if (arrsum(a,alen)==arrsum(b,blen))
{
printf("%d\n", arrsum(a,alen));
printf("%d\n", arrsum(b,blen));
return;
}
int tdiff;
tdiff = arrsum(a,alen)-arrsum(b,blen);
int i,j;
for(i=0;i<alen;i++)
{
for(j=0;j<blen;j++)
{
if(abs(2*(b[j]-a[i])+tdiff)<abs(tdiff))
{
swap(&a[i],&b[j]);
tug(a,b,alen,blen);
return;
}
}
}
printf("%d\n", arrsum(a,alen));
printf("%d\n", arrsum(b,blen));
return;
}
int main()
{
int n,i;
int a[50], b[50];
scanf("%d", &n);
if (n%2==0)
{
for(i=0;i<n/2;i++) scanf("%d", &a[i]);
for(i=0;i<n/2;i++) scanf("%d", &b[i]);
printf("\n");
tug(a,b,n/2,n/2);
}
else
{
for(i=0;i<(n+1)/2;i++) scanf("%d", &a[i]);
for(i=0;i<(n-1)/2;i++) scanf("%d", &b[i]);
printf("\n");
tug(a,b,(n+1)/2,(n-1)/2);
}
return 0;
}
import math
n = int(raw_input())
x = []
for i in range(n):
x.append(int(raw_input()))
S = sum(x)
m = n//2
K = S/2.
k = int(math.ceil(K))
T = [[[0 for i in range(k+1)] for i in range(m+1)] for i in range(n+1)]
def compare(A, B, K):
a = abs(A-K); b = abs(B-K)
if a <= b: return A
else: return B
def argmin(X):
m = min(X)
return X.index(m)
for i in range(1,n+1):
for j in range(1,m+1):
for l in range(k+1):
if i==1 or j==1:
T[i][j][l] = x[argmin(map(lambda(a): abs(a-l),x[:i]))]
elif l==0:
T[i][j][l] = sum(sorted(x[:i])[:min(i,j)])
else:
T[i][j][l] = compare(T[i-1][j][l], T[i-1][j-1][max(l-x[i-1],0)]+x[i-1], l)
A = T[n][m][k]
B = S-A
if A<=B: print A, B
else: print B, A
import random, math
def distribute2(list_people):
list_people.sort()
list_a=[]
list_b=[]
for i,var in enumerate(list_people):
if i%2:
list_b.append(var)
else:
list_a.append(var)
return not_switching(list_a,list_b,abs(sum(list_a)- sum(list_b)))
def not_switching(list_a,list_b,prev):
sum_a,sum_b=sum(list_a), sum(list_b)
minimizer,minimizer_differ=None,0
if sum_a>sum_b:
for i,i_val in enumerate(list_a):
for j,j_val in enumerate(list_b):
temp=2*(i_val-j_val)
# if prev-minimizer_differ >prev-temp and prev-temp>=0:
if prev-minimizer_differ >prev-temp and prev-temp>=0:
minimizer_differ=temp
minimizer=(i,j,i_val,j_val)
elif sum_a<sum_b:
for i,i_val in enumerate(list_a):
for j,j_val in enumerate(list_b):
temp=2*(j_val-i_val)
if prev-minimizer_differ >prev-temp and prev-temp>=0:
minimizer_differ=temp
minimizer=(i,j,i_val,j_val)
else:
return list_a,list_b
if not minimizer:
return list_a,list_b
else:
list_a=list_a[:minimizer[0]]+[minimizer[3]]+list_a[minimizer[0]+1:]
list_b=list_b[:minimizer[1]]+[minimizer[2]]+list_b[minimizer[1]+1:]
return not_switching(list_a,list_b,prev-minimizer_differ)
일단 dispense2의 리턴부분 전까지 매개변수로 들어온 사람들의 몸무게 리스트를 2개의 리스트로 나눕니다. 이때 2개의 리스트는 sort를 사용해 오름차순으로 배열된 리스트를 각각 낮은 수부터 번갈아가며 한개씩 넣어진 리스트들입니다.
그냥 2개로 나눠도 되지만 실행시간을 생각하면 이편이 훨더 낳습니다.
not_switch가 실제로 두 집단으로 나누는 부분입니다.
not은 아무 의미 없습니다. 메인스레드에서 접근하지 말라고 붙인 겁니다. 이 함수의 기능은 말 그대로 a와 b 집단에서 한명씩 교환하는 것입니다.
이 교환의 방식은 a와 b 집단에서 1명씩 뽑아 교환할때, 오차 즉 a집단과 b집단 각각의 합의 차이를 최소한으로 하는 a집단의 원소와 b 집단의 원소를 뽑아 두 원소를 서로가 교환하는 형식입니다.
예를 들자면 [45,49,62,84,94]집단이 있다고 하면 dis...에서(dispense2의 약자) [45,62,94][49,84]두개로 만들어 줍니다. dis...의 리턴 부분에서는 switch(not_switch의 약자)함수가 불러집니다
이때 각 리스트의 총합은 201, 133으로 오차는 68이 됩니다. 그러면 각 리스트에서 오차를 최대한으로 줄여주는 94와 49 요소가 교환됩니다. 이런식으로 계속 교환해 나가다 전의 오차보다 더 줄일수 없으면 거기서 switch가 종료됩니다.
실제로 해 보면 짝수의 경우에는 6개만 되면 +-10정도의 오차내에서 대부분 정렬이 가능하고 홀수는 9개 정도면 오차 +-10정도로 대부분 정렬되더군요 더도말고 12명 이상이면 대부분의 두 리스트의 합의 오차가 +-2이내로 할 수 있게 됩니다.(random 객체로 생성하는)
실제 사용을 위해서는
n=input("인원 수를 입력하시오 >")
weight=[]
if n.isdigit():
for i in range(int(n)):
weight.append(random.randint(40,100))
lis_a,lis_b=(distribute2(weight))
print(weight)
print(sum(lis_a),sum(lis_b))
print(lis_a,lis_b,'\n')
이런 식으로 입력하면 됩니다.
#Python 3.5
inputText='''3\n100\n90\n200\n\n6\n45\n55\n70\n60\n50\n75\n\n4\n92\n56\n47\n82\n\n5\n2\n3\n4\n7\n8\n\n4\n50\n50\n100\n200\n'''
def game(tl) :
p=tl[0]
h=tl[1:]
if p != len(h) :
print("입력값 에러.")
exit()
h.sort()
h.reverse()
result=[0,0]
count=0
while count < len(h) :
if count == 0 :
result[0] = h[1]
result[1] = h[0]
count = 2
if count > 1 :
if len(h) - count > 2 :
twoSmall = h[count+1] + h[count+2]
r0 = abs(( result[0] + twoSmall ) - (result[1] + h[count]))
r1 = abs(( result[1] + twoSmall ) - (result[0] + h[count]))
if r0 <= r1 :
result[1] += h[count]
result[0] += h[count+1]
count += 2
else :
result[0] += h[count]
result[1] += h[count+1]
count += 2
elif len(h) - count == 1 :
if result[0] > result[1] :
result[1] += h[count]
count += 1
else :
result[0] += h[count]
count += 1
else :
if result[0] > result[1] :
result[1] += h[count]
result[0] += h[count+1]
count += 2
else :
result[0] += h[count]
result[1] += h[count+1]
count += 2
print(result[0], result[1])
def tugofWar(t) :
temp_list=[]
t_list=t.split('\n')
for i in t_list :
if i == '' :
game(temp_list)
del temp_list[0:len(temp_list)]
else :
temp_list.append(int(i))
tugofWar(inputText)
두개의 그룹 A와 B로 나누고요 서로 스왑했을때 양측의 몸무게 차이를 줄일 수 있다면 스왑합니다. 그런 경우를 더 이상 찾을 수 없을 때가지 반복합니다.
def tug(p):
cut = len(p)/2
A=p[:cut]
B=p[cut:]
while True:
swapped = False
for ai in range(len(A)):
for bi in range(len(B)):
sumA=sum(A);sumB=sum(B)
if abs(sumA-sumB) > abs(sumA-sumB-2*A[ai]+2*B[bi]):
A[ai],B[bi] = B[bi],A[ai]
swapped = True
break
if swapped : break
if not swapped : break
return min(sum(A),sum(B)),max(sum(A),sum(B))
while 1:
n=input()
if not n : break
p=[int(raw_input()) for i in range(n)]
print tug(p)
from itertools import *
def cmpr(li):
c = combinations((x for x in range(len(li))), len(li)//2)
m = []
for x in c:
a = []
b = []
s = set(x)
ran = set(x for x in range(len(li)))
s = ran - s
for y in x:
a.append(li[y])
for z in s:
b.append(li[z])
if m == []:
m.append(a)
m.append(b)
if abs(sum(a)-sum(b)) < abs(sum(m[0])-sum(m[1])):
m[0] = a
m[1] = b
return sum(m[0]), sum(m[1])
while __name__ == '__main__':
num = int(input('사람 수: '))
pe = []
for i in range(num):pe.append(int(input('{0}명째: '.format(i+1))))
print(cmpr(pe))
컴비네이션 썼습니다. 파이썬 3.5.1
Ruby
Dynamic + Set으로 구현했습니다. 랜덤 100명으로 실행시 루비(5-6초), 크리스탈(1초) 근처로 처리됩니다.
require 'set'
def generate_sums_with(sums, weight, size=sums.size-2)
(size).downto(0).each {|cnt| sums[cnt].each {|s| sums[cnt+1].add(s+weight) } }
end
def balanced_tug
weights = (1..gets.to_i).map { gets.to_i }
sums = (0..weights.size).map { Set.new }.tap {|e| e[0].add(0) }
weights.each {|weight| generate_sums_with(sums, weight) }
sum = weights.reduce(:+)
balanced_one = sums[weights.size/2].min_by {|e| (sum-e*2).abs }
[balanced_one, sum-balanced_one].minmax.join(" ")
end
Ruby Test
# stdin test data
test_stdin = %w( 3 100 90 200
6 45 55 70 60 50 75
4 92 56 47 82
5 2 3 4 7 8
4 50 50 100 200).join("\n")
$stdin = StringIO.new(test_stdins)
expect( balanced_tug ).to eq "190 200"
expect( balanced_tug ).to eq "175 180"
expect( balanced_tug ).to eq "138 139"
expect( balanced_tug ).to eq "12 12"
expect( balanced_tug ).to eq "150 250"
#=> perfomance
require 'benchmark'
case_100 = ([100] + 100.times.map { Random.rand(1..450) }).join("\n")
$stdin = StringIO.new(case_100)
expect( Benchmark.realtime { balanced_tug } ).to be_between(0.0, 5.0)
or
Crystal
def generate_sums_with(sums, weight, size=sums.size-2)
(size).downto(0).each {|cnt| sums[cnt].each {|s| sums[cnt+1].add(s+weight) } }
end
def balanced_tug(weights)
sums = (0..weights.size).map { Set.new [] of Int32 }.tap {|e| e[0].add(0) }
weights.each {|weight| generate_sums_with(sums, weight) }
sum = weights.sum
balanced_one = sums[weights.size/2].min_by {|e| (sum-e*2).abs }
[balanced_one, sum-balanced_one].minmax.join(" ")
end
Crystal Test
require "benchmark"
require "spec"
describe ".balanced_tug perfomance" do
it "must end in 2 sec" do #=> 00:00:01.1212750
case_100 = 100.times.map { Random.rand(1..450) }.to_a
running_time = Benchmark.realtime { balanced_tug(case_100) }
( running_time < Time::Span.new(0,0,2.0) ).should be_true
end
end
//Delphi 2010 , n Group divide 포함.
procedure fnTugofWar(var Q: array of Integer; C_Arr, C_Div: Integer; Memo1: TMemo);
var
i: Integer;
function tug(var P: array of Integer; bSelfChange: boolean = False): string;
var
i, j, g, ai, bi, n1, n2, cut, k, nMax, nK: Integer;
A: array of array of Integer;
Cmp: array of array of boolean;
nA, sumA: array of Integer;
swapped, iswapped: boolean;
s: string;
function sum(nCnt, nGrp: Integer): Integer;
var
i: Integer;
begin
result := 0;
for i := 0 to nCnt do
result := result + A[i, nGrp];
end;
begin
// Generics.Collections, Generics.Defaults;
// Sort Data (경우의 수를 N^3 => NLogN or N^2로 줄임)
TArray.Sort<Integer>(Q, TComparer<Integer>.Default);
cut := ( high(P) + 1) div 2; // 49 -> 24
SetLength(A, high(P) + 1, C_Div); // 24
SetLength(nA, C_Div);
SetLength(sumA, C_Div);
SetLength(Cmp, C_Div, C_Div); // 상호 비교를 선택함.
// 데이터 초기화
for i := 0 to High(nA) do
nA[i] := -1;
for i := 0 to C_Div - 1 do
for j := 0 to C_Div - 1 do
Cmp[i, j] := true;
// Group별로 순차적으로 데이터 집어넣기
for i := 0 to High(P) do
begin
k := i mod C_Div;
nA[k] := nA[k] + 1;
A[nA[k], k] := P[i]; // k = Group No
end;
for i := 0 to C_Div - 1 do
sumA[i] := sum(nA[i], i);
while true do
begin
swapped := False;
// Multi For구문을 처리하는 방법은
for i := 0 to C_Div - 1 do
for j := 0 to C_Div - 1 do
if (i <> j) and (abs(sumA[i] - sumA[j]) > 1) and Cmp[i, j] then
begin
iswapped := False;
// 교환의 경우만
for ai := 0 to nA[i] do
if abs(sumA[i] - sumA[j]) > 1 then
for bi := 0 to nA[j] do
if abs(sumA[i] - sumA[j]) > abs(sumA[i] - sumA[j] - 2 * A[ai, i] + 2 * A[bi, j]) then
begin
k := A[bi, j] - A[ai, i];
Inc(sumA[i], k);
dec(sumA[j], k);
k := A[bi, j];
A[bi, j] := A[ai, i];
A[ai, i] := k;
swapped := true;
iswapped := true;
if abs(sumA[i] - sumA[j]) < 2 then
break;
end;
// 한쪽의 한 사람을 주어서 값이 줄어든다면
if sumA[i] > sumA[j] then
begin
n1 := i;
n2 := j;
end
else
begin
n1 := j;
n2 := i;
end;
k := sumA[n1] - sumA[n2];
if bSelfChange and (i > 1) and (k > 1) then
begin
nK := -1;
nMax := 0;
for ai := 0 to nA[n1] do
if A[ai, n1] <= k then
begin
if nMax < A[ai, n1] then
begin
nMax := A[ai, n1];
nK := ai;
end;
end;
if nK > -1 then
begin
dec(nA[n1]);
Inc(nA[n2]);
if nA[n1] >= nK then
A[nK, n1] := A[nA[n1] + 1, n1];
A[nA[n2], n2] := nMax;
dec(sumA[n1], nMax);
Inc(sumA[n2], nMax);
swapped := true;
iswapped := true;
end;
end;
Cmp[i, j] := iswapped;
if iswapped then
for k := 0 to C_Div - 1 do
begin
Cmp[i, k] := true; // 변경되면 다른 모듈과도 재비교
Cmp[k, j] := true; // 변경되면 다른 모듈과도 재비교
end;
end;
if not swapped then // 더이상 교환이 없으면 빠져나오기
break;
end;
s := '';
for i := 0 to C_Div - 1 do
s := s + format('%d, ', [sumA[i]]);
result := s;
Memo1.Lines.Add(result);
// exit;
if C_Arr <= 1000 then
for i := 0 to C_Div - 1 do
begin
s := '';
for j := 0 to nA[i] do
s := s + format('%d ', [A[j, i]]);
Memo1.Lines.Add('Group' + IntToStr(i + 1) + ' Members: ' + #13#10 + ' ' + s);
end;
end;
begin
Randomize;
tug(Q, False);
end;
procedure TForm4.btn줄달이기2Click(Sender: TObject);
var
Q: array of Integer;
i, C_Members, Group_Count: Integer;
begin
Memo1.Lines.Clear;
C_Members := 6;
Group_Count := 2; // n Group 분배
SetLength(Q, C_Members);
Q[0] := 45;
Q[1] := 55;
Q[2] := 70;
Q[3] := 60;
Q[4] := 50;
Q[5] := 75;
fnTugofWar(Q, C_Members, Group_Count, Memo1);
// Random
C_Members := 70;
Group_Count := 9; // n Group 분배
SetLength(Q, C_Members);
for i := 0 to C_Members - 1 do
Q[i] := Random(440) + 10;
fnTugofWar(Q, C_Members, Group_Count, Memo1);
end;
효율이 좋지는 않지만, 참가자 수가 최대 100명으로 제한되니, 반수로 두 그룹으로 나눈다음 그룹의 합을 더 적게 만들 수 있는 형태로 원소를 교환해나가는 식으로 작성했습니다.
def tug(ar:[int]) -> (int, int):
n = len(ar) // 2
ra, rb = ar[:n], ar[n:]
i,j = 0, 0
sa, sb = 0, 0
while True:
while True:
sa, sb = sum(ra), sum(rb)
t = abs(sa - sb)
if t is 0:
return sa, sb
td = abs((sa - ra[i] + rb[j]) - (sb - rb[j] + ra[i]))
if td < t:
ra[i], rb[j] = rb[j], ra[i]
t = td
j = 0
else:
j += 1
if j >= len(rb):
break
i, j = i + 1, 0
if i >= len(ra):
break
return sa, sb
def proc():
x = int(input())
ar = [int(input()) for _ in range(x)]
a, b = tug(ar)
a, b = (a, b) if a < b else (b, a)
print(a, b)
def main():
n = int(input())
for _ in range(n):
proc()
main()
C#으로 작성했습니다.
public bool[] GetTugOfWar(List<int> inputs, bool[] selected, bool[] solution, int minDiff, int index = 0)
{
// get size of selected
int selectedSize = 0;
for (int i = 0; i < inputs.Count; i++) if (selected[i]) selectedSize++;
if (selectedSize == inputs.Count / 2)
{
// check if diff < minDiff, update solution
int diff = GetDiff(inputs, selected);
if (diff < minDiff)
{
minDiff = diff;
for (int i = 0; i < inputs.Count; i++) solution[i] = selected[i];
}
}
// check if currentIndex == n and return
if (index >= inputs.Count) return solution;
// add curindex to selected
selected[index] = true;
GetTugOfWar(inputs, selected, solution, minDiff, index + 1);
// remove curindex from selected
selected[index] = false;
GetTugOfWar(inputs, selected, solution, minDiff, index + 1);
return solution;
}
public int GetDiff(List<int> inputs, bool[] selected)
{
int leftSum = 0;
int rightSum = 0;
for (int i = 0; i < inputs.Count; i++)
if (selected[i]) leftSum += inputs[i];
else rightSum += inputs[i];
return Math.Abs(rightSum - leftSum);
}
#include <stdio.h>
#include <stdlib.h>
void sort(int* value, int n);
void recursion(int value, int index, int n, int count, int* arr);
int sum = 0;
int min = 1000;
int* temp_team;
int* team;
void main(void) {
int hn = 0;
int n = 6;
scanf("%d",&n);
int* weight = (int*) malloc (sizeof(int) * n);
for(int i = 0; i<n; i++)
scanf("%d",&weight[i]);
for(int i = 0 ; i < n ; i++)
sum = sum + weight[i];
sort(weight, n);
if(n%2 != 0)
hn = n/2;
else
hn = n/2-1;
team = (int*) malloc (sizeof(int) * (hn));
temp_team = (int*) malloc (sizeof(int) * (hn));
for(int i = 0; i < n ; i++) {
temp_team[hn] = weight[i];
recursion(weight[i], i, n, hn, weight);
}
int out = 0;
for(int i = 0 ; i < (hn+1) ; i++) {
out = out + team[i];
}
if(out <= (sum-out))
printf("%d\t%d\n", out, sum-out);
else
printf("%d\t%d\n", sum-out, out);
}
void recursion(int value, int index, int n, int count, int* arr) {
int result = 0;
int tsum = value;
count--;
for(int i = (index+1); i < n ; i++) {
tsum = value;
tsum = tsum + arr[i];
temp_team[count] = arr[i];
if(count > 0) {
recursion(tsum, i, n, count, arr);
}
if(count == 0) {
result = sum - (2*tsum);
if(result < 0)
result = result * (-1);
if(min >= result && count==0) {
min = result;
for(int j = 0; j < n;j++)
team[j] = temp_team[j];
}
}
}
}
void sort(int* value, int n) {
int temp;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
if(value[j] > value[j+1] && j+1 < n) {
temp = value[j+1];
value[j+1] = value[j];
value[j] = temp;
}
}
}
}
count = 0
p_list = []
p1, p2, tp = [], [], []
while True:
count = int(input("Peoples?"))
if count <= 100:
break
else:
print ("max count is 100")
for i in range(count):
while True:
p_list.append(int(input("Weight?")))
if p_list[i] > 0 and p_list[i] <= 450:
break
else:
print ("0 < Weight <= 450")
p_list.sort()
mid = int(len(p_list)/2)
for i in range(mid) :
p1.append(p_list[i])
for j in range(len(p_list)-1,mid-1,-1) :
p2.append(p_list[j])
for i in range(len(p1)) :
for j in range(len(p2)) :
tptest = sum(p2)+p1[i]-p2[j]
if abs(sum(p2) - tptest) < abs(sum(p2) - sum(p1)) :
tp = []
tp.append(p1[i])
tp.extend(p2)
tp.remove(p2[j])
p1.remove(p1[i])
p1.append(p2[j])
p2 = tp
if sum(p1) > sum(p2):
print(sum(p2), sum(p1))
else :
print(sum(p1), sum(p2))
int main(void) { int arr[100] = {}; int num = 0, weight = 0; int avg = 0; int fir = 0, sec = 0; // 1팀 2팀 bool flag = false;
printf("인원수를 입력하세요 : (단, 3명 이상 입력하세요.)");
scanf_s("%d", &num);
printf("몸무게를 입력하세요 : ");
for (int i = 0; i < num; i++)
{
scanf_s("%d", &weight);
avg += weight;
arr[i] = weight;
}
arr[num] = 0; //홀수
///////////////////////////// 버블정렬
for (int i = 0; i < num - 1; i++)
{
for (int j = 0; j < num - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
if (!flag)
break;
}
// 버블 정렬 출력
if (num % 2 == 0)
{
for (int k = 0; k < num; k++)
printf("%d ", arr[k]);
printf("\n");
}
else
{
for (int k = 0; k < num + 1; k++)
printf("%d ", arr[k]);
printf("\n");
}
//////////////짝수///////////////////
if (num % 2 == 0)
{
// 팀구하기
for (int i = 0; i < num / 2; i++)
{
fir = arr[0 + i * 2] + arr[num - 1 - i * 2];
sec = arr[1 + i * 2] + arr[num - 2 - i * 2];
}
//중앙 값 팀으로 분배하기
if (num > 4)
{
if (fir > sec)
{
if (arr[num / 2 - 1] > arr[num / 2])
{
sec += arr[num / 2 - 1];
fir += arr[num / 2];
}
else {
fir += arr[num / 2 - 1];
sec += arr[num / 2];
}
}
else {
if (arr[num / 2 - 1] > arr[num / 2])
{
fir += arr[num / 2 - 1];
sec += arr[num / 2];
}
else {
sec += arr[num / 2 - 1];
fir += arr[num / 2];
}
}
}
printf("짝수 >> 1팀 평균 : %d // 2팀 평균 : %d \n", fir, sec);
}
else //홀수
{
fir = arr[num] + arr[num - 1];
// 팀구하기
if (num > 5)
{
for (int i = 0; i < num / 2 - 1; i++)
{
fir = arr[-1 * i * 2] + arr[num - 1 + i * 2];
sec = arr[0 + i * 2] + arr[num - 1 - i * 2];
}
}
else
{
sec = arr[0] + arr[num - 2];
}
//중앙 값 팀으로 분배하기
if (num > 3)
{
if (fir > sec)
{
if (arr[num / 2 - 1] > arr[num / 2])
{
sec += arr[num / 2 - 1];
fir += arr[num / 2];
}
else {
fir += arr[num / 2 - 1];
sec += arr[num / 2];
}
}
else {
if (arr[num / 2 - 1] > arr[num / 2])
{
fir += arr[num / 2];
sec += arr[num / 2 - 1];
}
else {
sec += arr[num / 2 - 1];
fir += arr[num / 2];
}
}
}
printf("홀수>> 1팀 평균 : %d / 2팀 평균 : %d \n", fir, sec);
}
return 0;
}
n=int(input())
people=[0 for i in range(n)]
for i in range(n):
a=input()
a=int(a)
people[i]=a
def hap(people):
total=0
n=len(people)
for i in range(n):
total+=people[i]
return total
if n%2!=0:
people.append(0)
n+=1
people.sort()
team1=[]
team2=[]
cnt=0
while n>0:
if cnt%2==0 and n>2:
team1.append(max(people))
team1.append(min(people))
people.pop(0)
people.pop()
n=len(people)
cnt=1
elif cnt%2!=0 and n>2:
team2.append(max(people))
team2.append(min(people))
people.pop(0)
people.pop()
n=len(people)
cnt=0
elif cnt%2!=0 and n==2 and len(team2)==0:
team2.append(max(people))
team2.append(min(people))
people.pop(0)
people.pop()
n=len(people)
cnt=0
elif n==2:
team1.append(max(people))
team2.append(min(people))
people.pop(0)
people.pop()
n=len(people)
cnt=1
print(hap(team1))
print(hap(team2))
[Python 3.6] 내림차순 정렬 후, 각 팀 몸무게 합 비교 배분
def divTeam(inData):
inArray = inData.strip().split("\n")
(pCnt, pDataArr) = (inArray[0], inArray[1:])
if int(pCnt) != len(pDataArr): print("invalid data"); return
pDataArr = [int(i) for i in pDataArr]
pDataArr.sort(reverse=True)
team1Sum = team2Sum = team1Cnt = team2Cnt = 0
for i in pDataArr:
if team1Cnt == team2Cnt:
if team1Sum < team2Sum: team1Sum += i; team1Cnt += 1
else: team2Sum += i; team2Cnt += 1
elif team1Cnt < team2Cnt: team1Sum += i; team1Cnt += 1
else: team2Sum += i; team2Cnt += 1
if team1Sum > team2Sum: (team1Sum, team2Sum) = (team2Sum, team1Sum)
print("{0} {1}".format(team1Sum, team2Sum))
inData = """
4
92
56
47
82
"""
divTeam(inData)
Python3
그냥.. 바꿀 게 없을 때까지 바꿉니다.
sum을 매번 구하는 게 비효율적인데 보기 좋으라고 놔뒀습니다.
def exchange(t1, t2):
s1 = sum(t1); s2 = sum(t2)
for i in range(len(t1)):
for j in range(len(t2)):
if abs(s1 - s2) > abs((s1-t1[i]+t2[j]) - (s2-t2[j]+t1[i])):
t1[i], t2[j] = t2[j], t1[i]
return True
return False
def partition(lst):
if len(lst) % 2 != 0:
lst.append(0) # "윤태호"님 컨닝. 멋진 아이디어! -_-)b
m = len(lst) // 2
t1 = lst[:m]; t2 = lst[m:]
while exchange(t1, t2):
pass
return sum(t1), sum(t2)
원래는 차가 최소인 페어를 구해서 배치하는 방법이나, 퀵정렬을 흉내낸 방법 등 여러가지로 생각해 봤는데 최적해를 구한다는 걸 증명을 못하겠네요.
마지막으로 생각한 방법이, 정렬해서 1팀 멤버 x를 갖고 2팀 멤버 중 "x와 가장 가까운 수"를 찾아서 어떻게 하면 되지 않을까.. 싶은데 생각이 더 나가질 못하네요. 어떻게 방법이 있을 것 같은데T.T
package tugOfWar;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;
public class TugOfWar {
@SuppressWarnings("rawtypes")
private ArrayList<ArrayList> setArray(int[] arr) {
ArrayList<Integer> first = new ArrayList<Integer>();
ArrayList<Integer> second = new ArrayList<Integer>();
for (int ele : arr) {
if (first.isEmpty())
first.add(ele);
else if (second.isEmpty())
second.add(ele);
else if (first.get(first.size() - 1) > second.get(second.size() - 1))
second.add(ele);
else
first.add(ele);
}
if (first.size() > second.size()) {
second.add(0);
second = (ArrayList<Integer>) second.stream().sorted().collect(Collectors.toList());
} else if (first.size() < second.size()) {
first.add(0);
first = (ArrayList<Integer>) first.stream().sorted().collect(Collectors.toList());
}
ArrayList<ArrayList> list = new ArrayList<ArrayList>();
list.add(first);
list.add(second);
return list;
}
@SuppressWarnings("rawtypes")
private ArrayList<ArrayList> swapArray(ArrayList<Integer> first, ArrayList<Integer> second) {
int minS = second.stream().mapToInt(m -> m).min().getAsInt();
for (int i = 0; i < first.size(); i++)
if (minS < first.get(i)) {
second.add(first.get(i));
first.add(minS);
first.remove(i);
second.remove(0);
break;
}
ArrayList<ArrayList> list = new ArrayList<ArrayList>();
list.add(first);
list.add(second);
return list;
}
@SuppressWarnings("unchecked")
public int[] tugOfWar(int[] arr) {
Arrays.sort(arr);
@SuppressWarnings("rawtypes")
ArrayList<ArrayList> list = setArray(arr);
ArrayList<Integer> first = list.get(0);
ArrayList<Integer> second = list.get(1);
int diff = Integer.MAX_VALUE;
int[] result = new int[2];
for (int j = 0; j < arr.length; j++) {
int sumF = first.stream().mapToInt(m -> m).sum();
int sumS = second.stream().mapToInt(m -> m).sum();
if (diff > Math.abs(sumF - sumS)) {
diff = Math.abs(sumF - sumS);
result[0] = sumF;
result[1] = sumS;
}
if (sumF == sumS)
return new int[] { sumF, sumS };
if (sumF != sumS) {
list = swapArray(first, second);
first = (sumF > sumS) ? list.get(0) : list.get(1);
second = (sumF > sumS) ? list.get(1) : list.get(0);
}
second = (ArrayList<Integer>) second.stream().sorted().collect(Collectors.toList());
first = (ArrayList<Integer>) first.stream().sorted().collect(Collectors.toList());
}
return result;
}
public static void main(String[] args) {
TugOfWar tow = new TugOfWar();
// @SuppressWarnings("resource")
// Scanner scanner = new Scanner(System.in);
// int n = scanner.nextInt();
// int[] array = new int[n];
// for (int i = 0; i < n; i++) {
// array[i] = scanner.nextInt();
// }
int[] array = { 45, 55, 70, 60, 50, 75 };
System.out.println(Arrays.toString(tow.tugOfWar(array)));
System.out.println(Arrays.toString(tow.tugOfWar(new int[] { 2, 3, 4, 7, 8 })));
System.out.println(Arrays.toString(tow.tugOfWar(new int[] { 92, 56, 47, 82 })));
System.out.println(Arrays.toString(tow.tugOfWar(new int[] { 50, 50, 100, 200 })));
System.out.println(Arrays.toString(tow.tugOfWar(new int[] { 100, 90, 200 })));
}
}
def subset(m, n):
result = list()
if n == 0:
return [[]]
elif n > len(m):
return []
else:
for i in range(len(m)):
for j in subset(m[i+1:], n-1):
result.append([m[i]] + j)
return result
def tugteam(m):
teams = subset(m, int(len(m)/2))
a = sum(m)/2
b = [abs(sum(i) - a) for i in teams]
c = sum(teams[b.index(min(b))])
result = [c, int(2*a-c)]
result.sort()
return result
a = list(map(int, input().split()))
print(tugteam(a))
파이썬 3.6
"""
아이디어 >
1. 한쪽 그룹이 n//2명인 모든 조합을 찾아 각 그룹 합의 차가 0이 될때까지 비교합니다.
2. 모든 조합을 찾을때까지 그룹 합의 차가 0이 되는 그룹이 없는 경우 합의 차가 최소인 조합을 찾습니다.
"""
def inputdata():
n = int(input(''))
data = [ int(input('')) for i in range(n) ]
return data
def TugOfWar(t):
tmp_1,group_a,tmp_2 = [],[],[]
tmp = data[t:]
for n in range(len(tmp)):
tmp_1.append(tmp[n])
if len(tmp_1) == len(data)//2:
for p in data:
if p not in tmp_1:
tmp_2.append(p)
group_a.extend(tmp_1)
if sum(group_a)-sum(tmp_2) == 0:
result = [sum(group_a),sum(tmp_2)]
result.sort()
print(result[0],result[1],"\n")
return
else:
sub.append([abs(sum(group_a)-sum(tmp_2)),group_a,tmp_2])
tmp_1.pop()
tmp_2,group_a = [],[]
else:
for i in tmp[n+1:]:
tmp_1.append(i)
if n != 0 and len(tmp_1) == len(data)//2:
for p in data:
if p not in tmp_1:
tmp_2.append(p)
group_a.extend(tmp_1)
if sum(group_a)-sum(tmp_2) == 0:
result = [sum(group_a),sum(tmp_2)]
result.sort()
print(result[0],result[1],"\n")
return
else:
sub.append([abs(sum(group_a)-sum(tmp_2)),group_a,tmp_2])
tmp_1.pop()
tmp_2,group_a = [],[]
if i == data[-1]:
tmp_1[1:] = []
t += 1
if t == len(data):
result = [sum(min(sub)[1]),sum(min(sub)[2])]
result.sort()
print(result[0],result[1],"\n")
return
else:
TugOfWar(t)
if __name__ == "__main__":
t,sub = 0,[]
case = [[100,90,200],[45,55,70,60,50,75],[92,56,47,82],[2,3,4,7,8],[50,50,100,200],[45,55,70,60,50,75,25,15,42,18,99,22]]
# data = inputdata()
# TugOfWar(t)
for data in case:
t,sub = 0,[]
print(data)
TugOfWar(t)
[100, 90, 200]
190 200
[45, 55, 70, 60, 50, 75]
175 180
[92, 56, 47, 82]
138 139
[2, 3, 4, 7, 8]
12 12
[50, 50, 100, 200]
150 200
[45, 55, 70, 60, 50, 75, 25, 15, 42, 18, 99, 22]
287 289
import java.util.Scanner;
public class TugofWar {
public static int arraySum(int[] param){
int sum = 0;
for(int i : param){
sum += i;
}
return sum;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
int[] array1 = new int[count/2];
int[] array2 = new int[count % 2 == 1 ? count/2 +1 : count/2];
for(int i=0; i<array1.length; i++){
array1[i] = sc.nextInt();
}
for(int i=0; i<array2.length; i++){
array2[i] = sc.nextInt();
}
sc.close();
int sum1 = arraySum(array1);
int sum2 = arraySum(array2);
for(int i=0; i<array1.length; i++){
for(int j=0; j<array2.length; j++){
if(Math.abs(sum1 - sum2) > Math.abs(sum1 - array1[i] + array2[j]) - Math.abs(sum2 + array1[i] - array2[j])){
int temp = array1[i];
array1[i] = array2[j];
array2[j] = temp;
sum1 = arraySum(array1);
sum2 = arraySum(array2);
}
}
}
if(sum1 < sum2){
System.out.print(sum1 + " ");
System.out.println(sum2);
}else{
System.out.print(sum2 + " ");
System.out.println(sum1);
}
}
}
SplitGroup <- function(x){
split_len <- ifelse(length(x)%%2==1, round((length(x)+0.1)/2), length(x)/2)
allcomb <- combn(length(x),split_len)
sum_list <- list()
for(i in 1:ncol(allcomb)){
sum_list[[i]] <- c(
sum(x[allcomb[,i]]),
sum(x[-allcomb[,i]])
)
}
diff_result <- unlist(lapply(sum_list, function(x) x[1]-x[2]))
idx <- which(diff_result == max(diff_result[which(diff_result<=0)]))
return(
c(sum(x[allcomb[,idx[1]]]),sum(x[-allcomb[,idx[1]]]))
)
}
> SplitGroup(c(100,90,200))
[1] 190 200
> SplitGroup( c(45,55,70,60,50,75))
[1] 175 180
> SplitGroup( c(2,3,4,7,8))
[1] 12 12
먼저 자료의 개수에 따라 2그룹으로 나눴습니다. 자료가 홀수개라면 한쪽에 1개 더 많게 배분 했습니다. 예) 5개 자료 -> 2, 3개 4개 자료 -> 2, 2개
그 다음 단순 무식하게 가능한 모든 조합을 만들고 두 그룹의 각각 합계를 계산했습니다.
두 그룹의 차이가 가장 0에 가까운 값을 찾은 후 인덱싱 하였습니다.
import java.util.Scanner;
public class Calculate {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("참가인원수 입력 : ");
int n = s.nextInt();
int [] a = new int [n/2]; // 참가인원수를 반으로 나눠 배열 생성
int [] b = new int [n/2+n%2]; // 참가인원이 홀수일때는 b배열에 1 추가
for(int i=0 ; i<n ; i++){
System.out.println((i+1)+"번째 인원 몸무게 입력 :");
if (i < n/2) a[i] = s.nextInt();
else b[i-n/2] = s.nextInt();
}
int totalA = sum(a); //최초 합계 계산
int totalB = sum(b); //최초 합계 계산
int tmp = 0;
for(int j=0 ; j<a.length ; j++){
for(int k=0 ; k<b.length ; k++){
if(Math.abs(totalA-totalB) > Math.abs( (totalA-a[j]+b[k]) - (totalB-b[k]+a[j]) )){
// 임시적으로 값을 교환해 계산한 결과가 교환전 결과보다 차이가 적을 때 실제 값 변경
tmp = a[j];
a[j] = b[k];
b[k] = tmp;
totalA = sum(a); // 치환 후 합계 계산
totalB = sum(b);
}
}
}
if (totalA > totalB ) System.out.println(totalB + " " + totalA );
else System.out.println(totalA + " " + totalB );
}
public static int sum(int[] list) {
int total = 0;
for(int i=0 ; i<list.length ; i++)
total +=list[i];
return total;
}
}
def tugOfWar(list:List[Int]):(Int, Int) = {
var w = list
if(list.length % 2 == 1) w = 0 :: w
var cnt = 0
var A = Array[Int]()
var B = Array[Int]()
for(a <- w.sorted){
if(cnt % 2 == 0) A = A :+ a
else B = B :+ a
cnt += 1
}
var minComp = Math.abs(B.sum - A.sum)
for(i <- 0 until A.length){
var index = -1
for(j <- 0 until B.length){
if(minComp > Math.abs(minComp - 2*B(j) + 2*A(i))){
minComp = Math.abs(minComp - 2*B(j) + 2*A(i))
index = j
}
}
if(index != -1) {
var temp = A(i)
A(i) = B(index)
B(index) = temp
}
}
(A.sum, B.sum)
}
println(tugOfWar(List(100, 90, 200)))
println(tugOfWar(List(45, 55, 70, 60, 50, 75)))
println(tugOfWar(List(92, 56, 47, 82)))
println(tugOfWar(List(2, 3, 4, 7, 8)))
println(tugOfWar(List(50, 50 ,100, 200)))
println(tugOfWar(List(1, 2, 3, 4, 5, 100)))
def tugOfWar(list:List[Int]):(Int, Int) = {
var w = list
if(list.length % 2 == 1) w = 0 :: w
var cnt = 0
var A = Array[Int]()
var B = Array[Int]()
for(a <- w.sorted){
if(cnt % 2 == 0) A = A :+ a
else B = B :+ a
cnt += 1
}
var minComp = Math.abs(B.sum - A.sum)
for(i <- 0 until A.length){
var index = -1
for(j <- 0 until B.length){
if(minComp > Math.abs(minComp - 2*B(j) + 2*A(i))){
minComp = Math.abs(minComp - 2*B(j) + 2*A(i))
index = j
}
}
if(index != -1) {
var temp = A(i)
A(i) = B(index)
B(index) = temp
}
}
(A.sum, B.sum)
}
println(tugOfWar(List(100, 90, 200)))
println(tugOfWar(List(45, 55, 70, 60, 50, 75)))
println(tugOfWar(List(92, 56, 47, 82)))
println(tugOfWar(List(2, 3, 4, 7, 8)))
println(tugOfWar(List(50, 50 ,100, 200)))
println(tugOfWar(List(1, 2, 3, 4, 5, 100)))
def tugOfWar(list:List[Int]):(Int, Int) = {
var w = list
if(list.length % 2 == 1) w = 0 :: w
var cnt = 0
var A = Array[Int]()
var B = Array[Int]()
for(a <- w.sorted){
if(cnt % 2 == 0) A = A :+ a
else B = B :+ a
cnt += 1
}
var minComp = Math.abs(B.sum - A.sum)
for(i <- 0 until A.length){
var index = -1
for(j <- 0 until B.length){
if(minComp > Math.abs(minComp - 2*B(j) + 2*A(i))){
minComp = Math.abs(minComp - 2*B(j) + 2*A(i))
index = j
}
}
if(index != -1) {
var temp = A(i)
A(i) = B(index)
B(index) = temp
}
}
(A.sum, B.sum)
}
println(tugOfWar(List(100, 90, 200)))
println(tugOfWar(List(45, 55, 70, 60, 50, 75)))
println(tugOfWar(List(92, 56, 47, 82)))
println(tugOfWar(List(2, 3, 4, 7, 8)))
println(tugOfWar(List(50, 50 ,100, 200)))
println(tugOfWar(List(1, 2, 3, 4, 5, 100)))
파이썬 입니다.
from itertools import combinations
n = int(input('please enter the number of people :'))
w, min_errors = [], []
result, result_list = [], []
for i in range(n): w.append(float(input('please enter the weight :')))
for i in range(n//2+1):
errors = [abs(sum(w)/2 - sum(ci)) for ci in combinations(w, i)]
min_error = min(errors)
for ci in combinations(w, i):
if min_error == abs(sum(w)/2 - sum(ci)): result_list.append(ci)
errors2 = [abs(sum(w)/2 - sum(results)) for results in result_list]
min_errors2 = min(errors2)
for results in result_list:
if min_errors2 == abs(sum(w)/2 - sum(results)):
print(sorted((sum(results), sum(w) - sum(results))))
class Program
{
static void Main(string[] args)
{
War war;
int nCnt = 0;
string strInput = string.Empty;
while (true)
{
var input = Console.ReadLine();
strInput += input.ToString() + " ";
string[] strSplit = strInput.Split(' ');
int total = int.Parse(strSplit[0]);
if (nCnt++ == total)
{
war = new War(strSplit);
break;
}
}
}
}
class War
{
public War(string[] strResult)
{
int nFstSum, nSecSum, nTotalSum, nImsiSum;
bool bCheck = false;
int nLength = int.Parse(strResult[0]);
int[] a = new int[nLength];
nFstSum = nSecSum = nTotalSum = nImsiSum = 0;
for (int i = 1, k = 0; i < strResult.Length - 1; i++)
{
if (strResult[i] != " ")
{
a[k] = int.Parse(strResult[i]);
nTotalSum += a[k];
}
k++;
}
Array.Sort(a);
Array.Reverse(a);
if (nTotalSum % 2 == 0)
{
for (int i = 0; i < a.Length; i += 2)
{
nImsiSum += a[i];
if (nTotalSum / 2 == nImsiSum && i > 1)
{
bCheck = true;
break;
}
}
}
if (bCheck)
{
nFstSum = nImsiSum;
nSecSum = nTotalSum / 2;
}
else
{
for (int i = 0, z = 0; i < a.Length; i++)
{
if (i == 0)
{
nFstSum = a[i];
}
else
{
if (z < 2)
{
nSecSum += a[i];
}
else
{
nFstSum += a[i];
if (z > 2)
z = 0;
}
z++;
}
}
}
if (nFstSum > nSecSum)
Console.WriteLine("{0}, {1}", nSecSum, nFstSum);
else
Console.WriteLine("{0}, {1}", nFstSum, nSecSum);
}
}
일일히 하는 것은 너무 오래걸릴 것 같아 random을 이용한 무차별 swap을 일정 횟수 진행하였습니다. 중간에 한동안 결과가 일정하면 정답으로 간주해 바로 출력하였고, random simulation이기 때문에 n이 100명이어도 1초내로 올바른 결과가 나옵니다. range(100000)부분과 count부분을 수정하여 시간이나 정확도를 조절합니다. (물론 n이 문제범위를 벗어날정도로 많이 커지면 현재 코드로는 버그가 생길 것 입니다)
import random
total_case = int(input()) #전체 case 수
for each_case in range(total_case): #각 case
num_total_people = int(input()) #해당 case의 줄다리기 사람 수
total_people = []
for i in range(num_total_people):
person_weight = int(input())
total_people.append(person_weight)
middle = len(total_people)//2
group1 = total_people[:middle] #전체를 2개의 그룹으로 나눈다
group2 = total_people[middle:]
count = 0 #충분히 돌린 것 같을 경우 break
#무작위 교체
for i in range(100000):
sum_group1 = sum(group1); sum_group2 = sum(group2)
sub = abs(sum_group1-sum_group2)
idx1 = random.randint(0,middle-1)
idx2 = random.randint(0,len(total_people)-middle-1)
group1[idx1], group2[idx2] = group2[idx2], group1[idx1] #무차별 swap
if(sub <= abs(sum(group1)-sum(group2))):
group1[idx1], group2[idx2] = group2[idx2], group1[idx1] #swap한 결과가 더 나쁠경우 원래대로 회복
count += 1
if(count > middle*1000): break #충분히 돌려도 결과가 같을 경우 break
else:
count = 0 #swap이 된 경우 count 초기화
if(sum(group1)==sum(group2)): break #같아도 break
sum_group1 = sum(group1); sum_group2 = sum(group2)
if(sum_group1>sum_group2):
print(sum_group2, sum_group1)
else:
print(sum_group1, sum_group2)
// 프로그램 순서 // 1. 배열 값들을 입력 받는다. // 2. 해당 배열을 정렬한다. // 3. 2개씩 묶어서 차이를 구한다. // 4. 가장 차이가 큰 순서대로 합이 큰것에는 작은값을, 합이 작은것에는 큰 값을 더해준다.
import java.util.Scanner;
import java.util.Arrays;
public class KimSanghyeop
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] arr= new int[num + num%2];
int f1;
for(f1=num%2;f1<arr.length;f1++)
{
arr[f1] = sc.nextInt();
}
Arrays.sort(arr);
int sum1=0,sum2=0;
int max=arr[1]-arr[0];
int cnt=0;
int temp;
int idx=0;
f1=0;
while(cnt < arr.length/2)
{
// 배열 앞뒤의 차이
max=0;
for(f1=0;f1<arr.length;f1+=2)
{
temp = arr[f1+1]-arr[f1];
if(temp >=max && arr[f1+1]!=0)
{
max = temp;
idx = f1;
}
}
//System.out.println("max : "+max + " / idx :"+idx);
// 차이가 가장 큰 순서대로 더해주기.
if(sum1 < sum2)
{
sum1 +=arr[idx+1];
sum2+=arr[idx];
}
else
{
sum2 +=arr[idx+1];
sum1+=arr[idx];
}
arr[idx] =0;
arr[idx+1]=0;
cnt+=1;
}
System.out.println("s1 : "+sum1);
System.out.println("s2 : "+sum2);
}
}
#include <iostream>
using namespace std;
int main(){
int w[100]={0,0,};
int wt[100]={0,0,};
int n, n1=0, n2=0, w1=0, w2=0, t=0;
int half , gap , cap;
cin >> n;
for(int i =0;i<n;i++) cin>>w[i]; //input
//sort
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(w[i]<w[j]){
t=w[i];
w[i]=w[j];
w[j]=t;
}
}
}
if(n%2) w[n++]=0;
//devide
for(int i=0;i<n;i++){
wt[i]= (w1<w2) ? 0 : 1;
if(wt[i]) w2+= w[i], n2++;
else w1 += w[i], n1++;
if(n2*2 == n)
{
for (int j = i+1;j<n;j++) wt[j]=0,n1++,w1+=w[j];
break;
}
if(n1*2 == n)
{
for (int j = i+1;j<n;j++) wt[j]=1,n2++,w2+=w[j];
break;
}
}
//adjust
gap = w1 < w2 ? w2- w1 : w2 - w1;
for(int i=0;i-1<n;i++){
if(wt[i]!=wt[i+1]){
cap= w[i] - w[i+1];
if(cap<gap){
t=wt[i];
wt[i]=wt[i+1];
wt[i+1]=t;
gap-=cap*2;
}
if(gap==0) break;
}
}
w1= w2 = 0;
for (int i=0;i<n;i++){
if(wt[i]) w2+=w[i]; else w1+=w[i];
}
cout<< w1 << '\t' <<w2 <<endl;
}
윤태호님의 알고리즘을 참고했습니다
def Tug_of_War(n):
lis,syn,t = [] if n%2 == 0 else [0],[0,0],[0,0]
for x in range(n):
lis.append(int(input()))
while lis != []:
t[0] = list(map(lambda n : abs(lis[0]-n), lis[1:]))
t = list(reversed(sorted([lis[0],lis[t[0].index(min(t[0]))+1]])))
lis.remove(t[0])
lis.remove(t[1])
syn[0],syn[1] = syn[0]+t[0],syn[1]+t[1]
syn.sort()
print(syn)
import itertools
peo_num = int(input("사람의 숫자 :"))
wts = []
for i in range(peo_num):
while True:
wt = int(input("{}번째 사람의 몸무게 : ".format(i+1)))
if 1 <= wt <= 450:
wts.append(wt)
break
else:
print('잘못된 입력입니다.')
acc_wt = sum(wts)
pro_wts = itertools.permutations(wts,peo_num//2)
for ran_set in pro_wts:
score = abs(sum(wts) - 2*sum(ran_set))
pre_score = abs(sum(wts) - 2*acc_wt)
if score < pre_score:
acc_wt = sum(ran_set)
if acc_wt >= sum(wts)-acc_wt:
num1 = sum(wts)-acc_wt
num2 = acc_wt
else :
num1 = acc_wt
num2 = sum(wts)-acc_wt
print(num1,num2)
처음에 이렇게 작성했었는데 모든 경우에 대해서 확인을 하는게 숫자가 커질수록 시간이 기하 급수적으로 걸려서 100명의 사람에 대해서는 작동을 안함
생각을 바꿔서 사람을 두그룹으로 나눠서 사람을 한명씩 바꾸면서 합의 차이가 작아지도록 만듬 사람을 한명만 바꾼다고 했을 때 최소값으로 무조건 가는지는 생각해보지 않음
import itertools
peo_num = int(input("사람의 숫자 :"))
wts = []
for i in range(peo_num):
while True:
wt = int(input("{}번째 사람의 몸무게 : ".format(i+1)))
if 1 <= wt <= 450:
wts.append(wt)
break
else:
print('잘못된 입력입니다.')
acc_wt = sum(wts)
pro_wts = itertools.permutations(wts,peo_num//2)
for ran_set in pro_wts:
score = abs(sum(wts) - 2*sum(ran_set))
pre_score = abs(sum(wts) - 2*acc_wt)
if score < pre_score:
acc_wt = sum(ran_set)
if acc_wt >= sum(wts)-acc_wt:
num1 = sum(wts)-acc_wt
num2 = acc_wt
else :
num1 = acc_wt
num2 = sum(wts)-acc_wt
print(num1,num2)
import random
peo_num = int(input("사람의 숫자 :"))
wts = []
for i in range(peo_num):
while True:
wt = int(input("{}번째 사람의 몸무게 : ".format(i+1)))
if 1 <= wt <= 450:
wts.append(wt)
break
else:
print('잘못된 입력입니다.')
part_num = peo_num//2
group_a = wts[:part_num]
group_b = wts[part_num:]
error = sum(wts)
error_list = list(range(500))
def odd():
global group_a, group_b, error, error_list, part_num
cnt = 0
while True:
cnt += 1
tem_a = group_a
tem_b = group_b
if cnt % 2 == 1:
num = random.randint(0,len(tem_b)-1)
tem_a.append(tem_b.pop(num))
else:
num = random.randint(0,len(group_a)-1)
tem_b.append(tem_a.pop(num))
if error >= abs(sum(group_a)-sum(group_b)):
error = abs(sum(group_a)-sum(group_b))
error_list.append(error)
group_a = tem_a
group_b = tem_b
if len(set(error_list[-500:]))==1:
if sum(group_a)<sum(group_b):
num1 = sum(group_a)
num2 = sum(group_b)
else :
num1 = sum(group_b)
num2 = sum(group_a)
print(num1,num2)
break
def even():
global group_a, group_b, error, error_list, part_num
cnt = 0
while True:
cnt += 1
tem_a = group_a
tem_b = group_b
num1 = random.randint(0,len(tem_b)-1)
tem_a.append(tem_b.pop(num1))
num2 = random.randint(0,len(group_a)-1)
tem_b.append(tem_a.pop(num2))
if error >= abs(sum(group_a)-sum(group_b)):
error = abs(sum(group_a)-sum(group_b))
error_list.append(error)
group_a = tem_a
group_b = tem_b
if len(set(error_list[-500:]))==1:
if sum(group_a)<sum(group_b):
num1 = sum(group_a)
num2 = sum(group_b)
else :
num1 = sum(group_b)
num2 = sum(group_a)
print(num1,num2)
break
def main():
if peo_num%2==0:
even()
elif peo_num%2==1:
odd()
main()
c++입니다. 재귀함수로, 2/n명으로 만들 수 있는 모든 경우의 수를 탐색해서 문제를 풀었습니다. 문제에서 주어지지 않은 다양한 예시에서도 답을 잘 구합니다. (모든 경우의 수이기 때문에... time complexity는 쓰레기지만요)
//
// main.cpp
// CPP_Project
//
// Created by 최세현 on 08/04/2019.
// Copyright © 2019 최세현. All rights reserved.
//
#include <iostream>
using namespace std;
int *arr;
int number, totalSum = 0, result = 0;
void findSum(int start, int sum, int n)
{
if(n == number/2)
{
if(abs(totalSum - sum) <= abs(result-totalSum))
result = sum;
return;
}
for(int i = start; i < number; i++)
findSum(i+1, sum+arr[i], n+1);
}
int main(int argc, const char * argv[]) {
// insert code here...
cin >> number;
arr = new int[number];
for(int i = 0; i < number; i++)
{
cin >> arr[i];
totalSum += arr[i];
}
totalSum /= 2;
findSum(0, 0, 0);
cout << result << " " << totalSum*2 - result << endl;
delete[] arr;
return 0;
}
사람수의 절반의 몸무게 합들 중, 전체몸무게를 2로 나눈 수를 넘지 않는 것들을 먼저 구하고 그중 가장 큰것을 구하는 방식으로 짜봤습니다... 사람수가 많아지니까 시간이 많이 걸려요..
from itertools import combinations
from math import ceil
nbs = list(raw_input('Numbers : ').split())
n = int(ceil(len(nbs) / 2.0))
cbs = list(combinations(nbs, n))
s = sum(int(x) for x in nbs)
re = []
print cbs
for i in cbs:
r = 0
for j in i:
r += int(j)
if r <= (s/2.0):
re.append(r)
print max(re), s-max(re)
from itertools import combinations
def weight(wl):
n = wl[0]
comb = combinations(wl[1:], int(round(n/2)))
l = list(comb)
l_sum = list()
for i in range(len(l)):
l_sum.append(sum(l[i]))
l_min = min(l_sum, key = lambda x: abs(x - sum(wl[1:])/2))
l_min_index = l_sum.index(l_min)
team1 = sum(l[l_min_index])
team2 = sum(wl[1:]) - team1
return (team1, team2)
Javascript(ES6)...
`멤버가 홀수인 경우 몸무게가 0 인 멤버를 한명 추가, 재귀 제너레이터 함수를 구현하여 팀을 나눌 수 있는 경우의 수(조합)을 구함, 구해진 모든 팀 케이스에서 몸무게 차이가 가장 적은 케이스를 출력`;
class Tug {
constructor(members) {
// 멤버가 홀수라면 몸무게가 0 인 가상멤버 추가
this.members = (members.length % 2 == 0) ? members : [...members, 0];
// 팀을 가를 수 있는 모든 케이스(조합)를 담은 배열
this.team_cases = this._find_team_cases();
}
// 팀을 나누는 모든 케이스(조합)를 구하는 재귀 제너레이터 함수
* _find_combinations(call_count, start, m_indices) {
let half = ~~(this.members.length / 2); // ~~( x ) 는 x 에서 소수점 이하 단위 절사
// 멤버의 절반이 한쪽 팀에 선택된 시점에 팀을 구분, [[...팀1멤버],[...팀2멤버]] 형태로 yield
if(call_count == half) {
let [team_1, team_2] = [[], []]
for(let i = 0; i < this.members.length; i++) {
if(m_indices.indexOf(i) > -1) {
team_1.push(this.members[i]);
} else {
team_2.push(this.members[i]);
}
}
yield [team_1, team_2];
}
// 아직 팀이 만들어지지 않았다면, 다음 멤버의 index 를 추가하여 재귀호출
// call_count 가 0 일때는 멤버를 전체 순회할 필요 없음
// (단순히 팀을 2개로 구분하기만 할 땐, call_count == 0 일때 전체 순회하면 중복요소가 나옴)
let limit = (call_count == 0) ? half : this.members.length;
for(let i = start; i < limit; i++) {
yield * this._find_combinations(call_count + 1, i + 1, [...m_indices, i]);
}
}
// 팀을 나누는 모든 케이스(조합)를 찾는 함수 (위 제너레이트 재귀함수 활용)
_find_team_cases() {
let team_cases = [];
for(let t of this._find_combinations(0, 0, [])) {
team_cases.push(t);
}
return team_cases;
}
// 몸무게 합의 차이가 가장 적은 팀조합 출력 함수
print_sum_of_each_team() {
// 각 팀의 몸무게 합을 구하여, 모든 케이스의 몸무게 합 배열 생성 (합계가 작은 것이 앞에 오도록 함)
let result = [];
for(let t of this.team_cases) {
let temp = [t[0].reduce((a, v) => a + v, 0), t[1].reduce((a, v) => a + v, 0)];
if(temp[0] > temp[1]) { [temp[0], temp[1]] = [temp[1], temp[0]]; }
result.push(temp);
}
// 몸무게 합의 차이가 제일 적은 순으로 정렬한 뒤, 제일 앞 요소 출력
result.sort((a, b) => (Math.abs(a[0] - a[1]) - Math.abs(b[0] - b[1])));
console.log(result[0]);
}
}
new Tug([100, 90, 200]).print_sum_of_each_team();
new Tug([45, 55, 70, 60, 50, 75]).print_sum_of_each_team();
new Tug([92, 56, 47, 82]).print_sum_of_each_team();
new Tug([2, 3, 4, 7, 8]).print_sum_of_each_team();
new Tug([50, 50, 100, 200]).print_sum_of_each_team();
Python 3...
from itertools import combinations
class Tug:
def __init__(self, members):
# 멤버 수가 홀수면 몸무게 0 인 가상멤버 추가
self.members = members if len(members) % 2 == 0 else members + [0]
# 모든 팀 나누기 케이스(조합) 리스트
self.team_cases = self.__find_team_cases()
# 팀 나누기 케이스 구하는 제너레이터(combinations 사용)
def __find_combinations(self):
team_1, team_2, team_maden = [], [], []
for m in combinations(self.members, len(self.members) // 2):
# 중복이 나오기 때문에 team_maden 으로 이미 만들어진 팀 케이스인지 검사
if list(m) not in team_maden:
team_1 = list(m)
team_2 = [x for x in self.members if x not in team_1]
team_maden.append(team_2)
yield [team_1, team_2]
# 팀 나누기 케이스 구하는 메인 함수
def __find_team_cases(self):
team_cases = []
for t in self.__find_combinations():
team_cases.append(t)
return team_cases
# 몸무게 차이가 가장 적은 케이스 출력 함수
def print_sum_of_each_team(self):
# 각 팀의 몸무게 합을 구한 배열 생성 (몸무게 합이 적은 팀이 앞으로 오도록 함)
result = []
for t in self.team_cases:
temp = [sum(t[0]), sum(t[1])]
if temp[0] > temp[1]:
temp[0], temp[1] = temp[1], temp[0]
result.append(temp)
# 몸무게 차이가 가장 적은 순으로 정렬한 뒤, 제일 앞 요소 출력
result.sort(key = lambda x: abs(x[0] - x[1]))
print(result[0])
Tug([100, 90, 200]).print_sum_of_each_team() # [190, 200]
Tug([45, 55, 70, 60, 50, 75]).print_sum_of_each_team() # [175, 180]
Tug([92, 56, 47, 82]).print_sum_of_each_team() # [138, 139]
Tug([2, 3, 4, 7, 8]).print_sum_of_each_team() # [12, 12]
Tug([50, 50, 100, 200]).print_sum_of_each_team() # [150, 200]
def inp() : # 사용자 입력
numb_p, w_list = int(input("N : ")), []
for i in range(numb_p) :
w_list.append(int(input("INPUT : ")))
w_list_1 = w_list[:int(len(w_list)/2)]
w_list_2 = w_list[int(len(w_list)/2):]
return numb_p, w_list_1, w_list_2
def det_min(D_list) : #2차원 리스트에서 최소값과 그 인덱스 반환
res = [min(D_list[0]), 0, D_list[0].index(min(D_list[0]))]
for th in D_list :
qwer = min(th)
if qwer < res[0] : res = [qwer, D_list.index(th), th.index(qwer)]
return res
def M_pr(N, w_L_1, w_L_2) :
mat, loc_min = [[0]*len(w_L_2) for i1 in w_L_1], float('inf')
#mat은 (각 요소의 차)-(보정해야하는 양, 즉 이상치로부터의 편차). 이 값이 0에 가까우면 해당 인덱스를 이용하여 스왑
#loc_min은 현재 최소값 (초기화)
while True : #최소값을 찾을 떄 까지 반환
ave = (sum(w_L_1)+sum(w_L_2))/2
w_L_1_D, w_L_2_D = sum(w_L_1)-ave, sum(w_L_2)-ave
for pos in w_L_1 :
mat[w_L_1.index(pos)] = (list(map(lambda x : abs(pos -x -w_L_1_D), w_L_2)))
min_in_iter = det_min(mat)
if min_in_iter[0] < loc_min : #현재까지의 반복으로 구해진 최소값보다 이번 반복에 구해진 최소값이 더 작다면(이전까지의 반복보다 두 집합의 차이를 더 줄일 수 있다면) :
tent = w_L_1[min_in_iter[1]]
w_L_1[min_in_iter[1]] = w_L_2[min_in_iter[2]]
w_L_2[min_in_iter[2]] = tent #둘을 교환한다
loc_min = min_in_iter[0] #최소값을 갱신한다
else :
return sum(w_L_1), sum(w_L_2)
# 이중 리스트 구조에서 최소값 인덱스 확인 후, 전회의 이터레이션에서 계산된 최소값보다 '작은' 경우만 갱신. 작은 값 존재하지 않으면 현재 조합 반환
return ave, w_L_1_D, w_L_2_D
q, w, e = inp()
print(M_pr(q, w, e))
처음에 입력된 순서대로 두 집합으로 나눈 다음, 두 집합의 합이 최대한 가까워질 때 까지 교환 가능한 요소들을 교환하는 식으로 만들었습니다.
결과
N : 3
INPUT : 100
INPUT : 90
INPUT : 200
N : 6
INPUT : 45
INPUT : 55
INPUT : 70
INPUT : 60
INPUT : 50
INPUT : 75
N : 4
INPUT : 92
INPUT : 56
INPUT : 47
INPUT : 82
N : 5
INPUT : 2
INPUT : 3
INPUT : 4
INPUT : 7
INPUT : 8
N : 4
INPUT : 50
INPUT : 50
INPUT : 100
INPUT : 200
(200, 190)
(175, 180)
(138, 139)
(12, 12)
(150, 250)
#include <iostream>
#include <cmath>
using namespace std;
void tug(int*, int*, int, int);
void swap(int&, int&);
int arrsum(int*, int);
int main() {
int N;
cin >> N;
int* a;
int* b;
if(N%2==0) {
a=new int[N/2];
b=new int[N/2];
for(int i =0;i<N/2;i++) cin >> a[i];
for(int i =0;i<N/2;i++) cin >> b[i];
tug(a, b, N/2, N/2);
}
else {
a=new int[(N+1)/2];
b=new int[(N-1)/2];
for(int i =0;i<(N+1)/2;i++) cin >> a[i];
for(int i =0;i<(N-1)/2;i++) cin >> b[i];
tug(a, b, (N+1)/2, (N-1)/2);
}
return 0;
}
void tug(int* a, int* b , int alen, int blen) {
int Asum = arrsum(a, alen);
int Bsum = arrsum(b, blen);
if (Asum ==Bsum) {
cout << Asum << endl << Bsum << endl;
return;
}
int diff = Asum-Bsum;
for(int i =0;i<alen;i++) {
for(int j =0;j<blen;j++) {
if (abs((b[j]-a[i])*2+diff) < abs(diff)) {
swap(a[i], b[j]);
tug(a, b, alen, blen);
return;
}
}
}
cout << Asum << endl << Bsum << endl;
return;
}
void swap(int& a, int& b) {
int tmp=a;
a=b;
b=tmp;
}
int arrsum(int* arr, int len) {
int sum=0;
for(int i =0;i<len;i++) {
sum+=arr[i];
}
return sum;
}
from itertools import combinations
def Tug(i):
w=0
a=[]
diff=[]
if i>100:
exit()
while w<i: # 숫자 대입받기
b=int(input("무게를 입력 : "))
if 1>b or b>450: # 몸무게 조건
break
a.append(b)
w+=1
r=i//2
s=sum(a)/2
total = combinations(a,r) # 조합이용해서 경우의수 찾기
for i in total:
diff.append(abs(s-sum(i)))
print(int(s-min(diff)),int(s+min(diff)))
Tug(int(input("인원을 입력하세요 : ")))
# Tug of War
def input_weight():
num_person = int(input())
if num_person > 100:
exit('Max person <= 100')
else:
list_weight = []
for i in range(num_person):
weight = int(input())
if weight < 1 or weight > 450:
exit('1 <= weight <= 450')
else:
list_weight.append(weight)
list_weight.sort()
list_weight.reverse()
return list_weight
def grouping(list_weight):
list1 = []
list2 = []
for x in list_weight:
if len(list1) == len(list2):
if sum(list1) >= sum(list2):
list2.append(x)
else:
list1.append(x)
elif len(list1) < len(list2):
list1.append(x)
else:
list2.append(x)
if sum(list1) == sum(list2) and abs(list1[-1] - list2[-1]) < x:
temp = list1.pop()
list1.append(list2.pop())
list2.append(temp)
print(sum(list1), sum(list2))
while True:
weights = input_weight()
grouping(weights)
경기자들 몸무게의 조합을 만들고 각 조합(party)의 합과 다른 party의 합의 차가 가장 작은 조합을 선택
# Python 3.11 이용
# 데이터를 입력하는 부분
while True:
if 1 <= (n := int(input('경기 인원수 : '))) <= 100: break
weight_lst = []
while True:
if 1 <= (weight := int(input('각 선수의 몸무게 : '))) <= 450:
weight_lst.append(weight)
if len(weight_lst) == n: break
# 입력된 데이터를 이용하여 처리하는 부분
import itertools
m = n // 2
total_wgt = sum(weight_lst)
# 경기자들 몸무게의 조합을 만듦 (combination)
for idx, ele in enumerate(list(itertools.combinations(range(n), m))):
team_sum = 0
for a in ele:
team_sum += weight_lst[a]
gap = abs(total_wgt - team_sum - team_sum)
if idx == 0: min = gap
elif min > gap:
min = gap
party = ele
wgt_sum = team_sum
wgt_sorted = sorted([wgt_sum, total_wgt - wgt_sum])
print(wgt_sorted)
def separate(lst1, lst2, p):
if len(p)==0:
return
if len(p)==1:
if lst1[-1]>=lst2[-1]:
lst2.append(p.pop(-1))
else:
tmp = lst2.pop(-1)
lst2.append(lst1.pop(-1))
lst2.append(p.pop(-1))
lst1.append(tmp)
return
lst2.append(p.pop(-1))
d = abs(sum(lst2)-sum(lst1))
idx=0
for i in range(len(p)):
if d > abs(sum(lst2)-sum(lst1)-p[i]):
d = abs(sum(lst2)-sum(lst1)-p[i])
idx = i
lst1.append(p.pop(idx))
if sum(lst1)>=sum(lst2):
separate(lst1, lst2, p)
else:
separate(lst2, lst1, p)
# inp = """3
# 100
# 90
# 200"""
# inp = """6
# 45
# 55
# 70
# 60
# 50
# 75"""
# inp = """4
# 92
# 56
# 47
# 82"""
# inp = """5
# 2
# 3
# 4
# 7
# 8"""
inp = """4
50
50
100
200"""
inp_split = inp.split('\n')
n = int(inp_split[0])
p = []
hap = 0
for i in range(n):
p.append(int(inp_split[i+1]))
p = sorted(p)
lst1 = [p.pop(-1)]
lst2 = [p.pop(-1)]
separate(lst1, lst2, p)
if sum(lst1)<=sum(lst2):
print(sum(lst1), ' ', sum(lst2))
else:
print(sum(lst2), ' ', sum(lst1))
n=int(input())
if n<=100:
if n==1:
list_weight=[0 for a in range(n+1)]
else:
list_weight=[0 for a in range(n)]
line=0
weight=0
while(line<n):
weight=int(input())
if weight>=1 and weight<=450:
list_weight[line]=weight
line+=1
print(list_weight)
list_weight.sort(reverse=True)
print(list_weight)
list_string_left=list()
list_string_right=list()
temporary=0
a=0
list_string_left.append(list_weight[a])
list_string_right.append(list_weight[a+1])
a=2
for b in range(2,(len(list_weight)-1),2):
if list_string_left[a-2]<list_string_right[a-2]:
list_string_left.append(list_weight[b])
list_string_right.append(list_weight[b+1])
else:
list_string_left.append(list_weight[b+1])
list_string_right.append(list_weight[b])
if sum(list_string_left)==sum(list_string_right) and ((n%2)==1 or ((n%2)==0 and a!=(n-2))):
temporary=list_string_left[a-1]
list_string_left[a-1]=list_string_right[a-1]
list_string_right[a-1]=temporary
a+=1
if (len(list_weight)%2)==1:
if sum(list_string_left)>sum(list_string_right):
list_string_right.append(list_weight[(len(list_weight)-1)])
else:
list_string_left.append(list_weight[(len(list_weight)-1)])
print("string left:",list_string_left)
print("string right:",list_string_right)
if sum(list_string_left)>=sum(list_string_right):
print(sum(list_string_right),sum(list_string_left))
else:
print(sum(list_string_left),sum(list_string_right))
JAVA입니다.
package tug_of_war;
import java.util.ArrayList;
import java.util.List;
public class Combination { //가능한 인덱스의 조합을 구하는 클래스
List<List<Integer>> selections;
public Combination() {
selections = new ArrayList<List<Integer>>();
}
void getSelection(int n, int r, List<Integer> selection) { //nCr의 모든 숫자 조합
for (int i = (selection.size() == 0) ?
0 : (selection.get(selection.size() - 1) + 1); i < n; i++) {
List<Integer> newSelection = new ArrayList<Integer>();
newSelection.addAll(selection);
newSelection.add(i);
if(newSelection.size() == r) {
selections.add(newSelection);
}
else {
getSelection(n, r, newSelection);
}
}
}
}
package tug_of_war;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Tug_of_War {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
List<Integer> members = new LinkedList<Integer>();
int len = sc.nextInt(); //총 인원수
for (int i = 0; i < len; i++) {
members.add(sc.nextInt());
}
Combination cb = new Combination();
cb.getSelection(len, len/2, new ArrayList<Integer>());
List<List<Integer>> selections = cb.selections;
int minDiff = 450*len; //몸무게 차이의 최댓값
List<List<Integer>> minDiffComb = new ArrayList<List<Integer>>(); //최소일 때의 조합
for (List<Integer> selection : selections) {
List<Integer> team1 = new ArrayList<Integer>();
List<Integer> team2 = new ArrayList<Integer>();
for (int i = 0; i < len; i++) {
if(selection.contains(i)) {
team1.add(members.get(i));
}
else {
team2.add(members.get(i));
}
}
if(Math.abs(sum(team1) - sum(team2)) < minDiff) {
minDiff = Math.abs(sum(team1) - sum(team2));
minDiffComb.clear();
minDiffComb.add(team1);
minDiffComb.add(team2);
}
}
int sum1 = sum(minDiffComb.get(0));
int sum2 = sum(minDiffComb.get(1));
System.out.println((sum1 >= sum2) ? (sum2 + " " + sum1) : (sum1 + " " + sum2));
sc.close();
}
static int sum(List<Integer> list) {
int sum = 0;
for (Integer integer : list) {
sum += integer;
}
return sum;
}
}