반응형
두 부분집합의 균형 맞추기
- 사용자로부터 집합 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)가 더 작아지면 바꿔주는 방식으로 최소값을 찾았다.
- 문제 해결을 위해 다른 함수를 정의해 사용하는 것은 복잡한 문제에서는 흔하다. 익숙해질 필요가 있다.
반응형
'💻 CS > 알고리즘 연습' 카테고리의 다른 글
[알고리즘 연습] 온도의 최대값 (by C++) (0) | 2021.01.12 |
---|---|
[알고리즘 연습] 요세푸스 문제 (0) | 2020.08.23 |
[알고리즘 연습] 멱집합 (0) | 2020.08.07 |
[알고리즘 연습] 회의실 배정 (0) | 2020.08.06 |
[알고리즘 연습] 괄호의 점수 (0) | 2020.08.01 |