문제 1026 · 중급 5
스터디 두 팀
완전 탐색 · 백트래킹 · 비트마스크
테스트별 제한 2000ms · 브라우저 채점
문제
알고리즘 스터디원 N명(N 은 짝수)을 인원이 같은 두 팀으로 나누려 한다. i번째 사람의 실력 점수는 a_i 다. 두 팀의 실력 합 차이가 가능한 한 작아야 한다. 그런데 '이 둘은 같은 팀이어야 한다' 는 요청이 M개 들어왔다. 요청은 이어진다. 1과 2가 같은 팀, 2와 3이 같은 팀이면 1과 3도 같은 팀이다. 요청을 모두 지키면서 두 팀의 실력 합 차이의 최솟값을 구하라. 요청을 모두 지키며 인원을 똑같이 나눌 수 없으면 -1 을 출력한다.
입력
첫째 줄에 N 과 M 이 주어진다. (2 ≤ N ≤ 16, N 은 짝수, 0 ≤ M ≤ 20) 둘째 줄에 a_1 … a_N 이 주어진다. (1 ≤ a_i ≤ 100) 다음 M개 줄에 같은 팀이어야 하는 두 사람의 번호 u, v 가 주어진다. (1 ≤ u, v ≤ N) u 와 v 가 같을 수도 있고, 같은 요청이 여러 번 나올 수도 있다.
출력
실력 합 차이의 최솟값을 출력한다. 불가능하면 -1 을 출력한다.
예제 입력 1
4 1 1 2 3 4 1 4
예제 출력 1
0
예제 입력 2
4 2 5 5 5 5 1 2 2 3
예제 출력 2
-1
힌트 펼치기
- 먼저 요청으로 이어진 사람들을 한 묶음으로 만들자. 묶음은 통째로 한 팀에 들어간다.
- 묶음은 많아야 16개다. 어떤 묶음을 첫 팀에 넣을지 2^(묶음 수) 가지를 모두 보고, 인원이 N/2 인 경우만 따지면 된다.
관련 장
풀이 작성
코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.
풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.
로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.