[알고리즘 연습] 두 부분집합의 균형 맞추기

두 부분집합의 균형 맞추기

• 사용자로부터 집합 data를 입력받는다
• 입력받은 집합 data를 A, B 둘로 나눈다.
• A와 B의 개수는 맘대로 정할 수 있다. (5개의 집합을 3개, 2개로 나누든 1개, 4개로 나누든 상관없다는 뜻이다.)
• A와 B의 요소도 맘대로 정할 수 있다. ([1,2,3,4,5] 집합을 [1,3,5]와 [2,4]로 나누는 것도 가능하다.)
• 단 A와 B를 합쳤을 때는 반드시 data의 요소를 모두 가져야 한다.
• 이 때 'A요소들의 합 - B 요소들의 합' 절댓값의 최솟값을 찾아라. (A, B를 찾을 필요는 없다.)

---

풀이

def getPowerSet(n,k):
    if n == k:
        return [[k]]

    basic = k        
    result = [[basic]]
    k += 1
    while (n >= k):
        for i in getPowerSet(n,k):
            result.append([basic] + i)
        k += 1

    return result

def powerSet(n) :
    result = []
    for i in range(1,n+1):
        result += getPowerSet(n,i)
    return result

def makeEqual(data) :
    if len(data) == 0:
        return 0
    combinations = powerSet(len(data))
    whole_sum = sum(data)
    min_AB = max(data)
    for combination in combinations:
        now_sum = 0
        for i in combination:
            now_sum += data[i-1]
            AB = (2*now_sum) - whole_sum 
            if (AB < 0 ):
                AB *= -1
            if (AB < min_AB):
                min_AB = AB
    return min_AB

def main():
    data = [int(x) for x in input().split()]

    print(makeEqual(data))

• 멱집합(모든 부분집합의 집합)을 이용한다는 생각을 못해 매우 헤맨 문제이다.
• 해설의 멱집합 이용 힌트를 보고나서야 풀 수 있었다.
• 사용자가 입력한 전체 집합의 길이(len(data))를 사용해 1~len(data) 집합의 멱급수를 구했다.
• 그리고 그렇게 구한 멱급수를 활용해 반복문을 돌면서 부분집합의 각 숫자를 인덱스로 활용해 가능한 A의 모든 케이스를 체크하고 그 합을 구했다.
• A-B = 2A - DATA (B = DATA-A) 이므로 그를 활용해 계산을 최소화했다. (AB = (2*now_sum) - whole_sum)
• 절댓값이 최소인 경우이므로 음수일 경우 -1을 곱해 양수로 변환했다. (if (AB < 0 ): AB *= -1)
• 최소 절대값의 최초값은 사용자 입력 집합의 최대값으로 설정하고 반복문을 돌면서 A-B절댓값(AB)가 더 작아지면 바꿔주는 방식으로 최소값을 찾았다.
• 문제 해결을 위해 다른 함수를 정의해 사용하는 것은 복잡한 문제에서는 흔하다. 익숙해질 필요가 있다.