8007 : 사과 분할
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 사과가 있고 각 사과의 무게가 주어집니다.
이 사과들을 두 그룹으로 나누어, 두 그룹의 무게 합의 차이가 최소가 되도록 하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 20$
• $1 \le p_i \le 10^9$ (각 사과의 무게)
이 사과들을 두 그룹으로 나누어, 두 그룹의 무게 합의 차이가 최소가 되도록 하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 20$
• $1 \le p_i \le 10^9$ (각 사과의 무게)
입력 설명
첫째 줄에 사과의 개수 $N$이 주어집니다.
둘째 줄에 $N$개의 정수 $p_1, p_2, \ldots, p_N$이 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수 $p_1, p_2, \ldots, p_N$이 공백으로 구분되어 주어집니다.
출력 설명
두 그룹의 무게 합의 차이의 최솟값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
3 2 7 4 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1도움
$N \le 20$이므로 비트마스크 또는 재귀 백트래킹을 사용하여 $2^N = 2^{20} \approx 10^6$가지의 모든 부분집합 분할을 완전 탐색하면 충분히 시간 내에 해결할 수 있습니다.