Tug of War

설명

회사 야유회에서 줄다리기를 하기로 했다. 야유회에 참가한 사람들을 두 편으로 공평하게 나눈다. 모든 사람들이 둘 중 한 편에 참여해야 하며, 두 편의 사람 수는 한 명이 넘게 차이가 나면 안 된다. 그리고 양 편에 속한 사람들 체중의 총합 차를 최소한으로 줄여야 한다.

입력

첫번째 라인은 줄다리기에 참여하는 모든 사람의 수(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

2014/02/14 11:10

길가의풀

@Katherine 님, (2,3,4,7,8) 총 5명이니까 (8,4) vs (2,3,7) 하면 12 vs 12 가 되어 공평해 보입니다 - 길가의풀, 2014/02/19 08:42 M D
아^^ 네 제가 틀렸네요^^;; 감사합니다 - Katherine, 2014/02/19 09:00 M D
으헉 ㅋㅋㅋㅋ 맨위의 입력값 주어지는 부분까지 세야하는 줄 알았다.... 답이 안나오더라 ㅋㅋㅋㅋ - Graed, 2015/09/24 03:29 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

26개의 풀이가 있습니다. 3 / 3 Page

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))

2016/11/16 19:40

바바

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

include

include

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

이진탐색을 사용하는 sortedlist 입니다. 나중에 쓸 데 있을까 싶어서 남겨봐요.


class SortedList(list):
    def __init__(self, lst = []):
        super().__init__(sorted(lst))

    # binary search
    # item을 못 찾으면 오류나는 대신 가장 가까운 index(삽입할 자리)를 리턴
    def __index(self, start, end, item):
        m = (start + end) // 2        
        if start > end: 
            return -1
        elif (self[m] == item): 
            return m
        elif (item <= self[m]):
            ret = self.__index(start, m-1, item)
            return ret if ret >= 0 else m
        else:
            ret = self.__index(m+1, end, item)
            return ret if ret >= 0 else m + 1

    def index(self, item):
        return self.__index(0, len(self) - 1, item)

    def append(self, item):
        self.insert(self.index(item), item)

    def remove(self, item):
        self.pop(self.index(item))
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
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;
    }

}

2017/08/04 18:45

SH

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 26
python x 13
기 타 x 4
lisp x 1
java x 2
r x 1
cpp x 2
ruby x 1
delphi x 1
cs x 1