Problem 105

출제 일시 : 2013-01-29 16:51:30

크기가 n인 집합 A의 원소들을 모두 더한 값을 S(A)라고 합시다. A의 부분집합 중 공집합이 아니고 서로소인 임의의 집합 B, C가

  1. S(B) ≠ S(C)
  2. B가 가진 원소의 개수가 C보다 많다면 S(B) > S(C)

라는 두 가지 조건을 만족하면 이 집합을 '특수합 집합'이라고 부르겠습니다.

예를 들어 {81, 88, 75, 42, 87, 84, 86, 65}는 65+87+88 = 75+81+84이므로 특수합 집합이 아닙니다. 반면 {157, 150, 164, 119, 79, 159, 161, 139, 158}은 두 가지 조건을 모두 충족하므로 특수합 집합이며, 이 때 S(A)=1286이 됩니다.

4K짜리 텍스트 파일(sets.txt)에는 7~12개의 원소를 가진 집합 100개가 입력되어 있습니다(그 중 첫 두줄 데이터는 위에 소개된 예제와 같습니다). 이들 중 특수합 집합 A1, A2, ..., Ak를 찾아 원소의 총합인 S(A1) + S(A2) + ... + S(Ak)를 구하시오.

주) 103번과 106번 문제가 본 문제와 연관되어 있습니다.



로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.