🔥

문제

민준이는 반 학생들에게 N 개의 무게를 알고 있는 사과를 나누어주고자 한다.
가지고 있는 사과를 적당히 나누어, 남학생들과 여학생들에게 각각 주고자 한다.
이 때, 학생들이 싸우는 것을 막기 위해서 남학생들에게 준 사과의 무게 합과, 여학생들에게 준 사과의 무게 합의 차이가 최소가 되도록 하고 싶다.
민준이를 위해, 가능한 무게 합의 차이의 최소를 출력해주자!

입력

첫번째 줄에는 사과의 수 N이 주어진다. (1≤N≤20) 두번째 줄에는, 각 사과의 무게 p(i) 가 주어진다. (1≤p(i)≤10^9)

출력

가능한 무게 합의 차이의 최소를 출력한다.

예제 1 입력

5
3 2 7 4 1

예제 1 출력

1

예제 2 입력

5
1 2 3 4 5

예제 2 출력

1

Source

import sys

n = int(input())
apples = list(map(int, input().split()))
result = sys.maxsize

# _sum: 남, 여 그룹 사과의 무게 차이
def dfs(k, _sum):
	global result

	if(k == n):
		if(abs(_sum) < result):
			result = abs(_sum)
		return
	dfs(k + 1, _sum + apples[k])
	dfs(k + 1, _sum - apples[k])

dfs(0, 0)
print(result)

참고