4160번 - 이혼 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 30 초 | 128 MB | 246 | 72 | 49 | 27.684% |
문제
잭과 질은 이혼을 하게 되었고, 두 사람은 재산을 공평하게 나누려고 한다. 두 사람은 집을 N채 가지고 있고, 각 집의 가치는 1,000,000달러 보다 크거나 같고, 40,000,000보다 작거나 같다. 잭은 일부 집을 가져가고, 질도 일부 집을 가져간다. 남은 집은 판다.
잭이 가져가는 집의 가치의 합은 질의 합과 같아야 한다. 공평하게 나누는 경우가 여러 가지라면, 각 사람이 가진 집의 가치의 합을 가장 크게 하려고 한다.
집 N채의 가치가 주어졌을 때, 팔아야 하는 집의 가치를 구하는 프로그램을 작성하시오.
입력
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 집의 수 N이 주어진다. 집의 수는 24개를 넘지 않는다. 다음 N개 줄에는 집의 가치가 주어진다.
입력의 마지막 줄에는 0이 주어진다.
출력
각 테스트 케이스마다, 집을 공평하게 나누기 위해 팔아야 하는 집의 가치를 출력한다.
예제 입력 1
5 6000000 30000000 3000000 11000000 3000000 0
예제 출력 1
41000000
힌트
문제의 예제는 잭과 질이 가지고 있는 집 5채의 가치가 6,000,000, 30,000,000, 3,000,000, 11,000,000, 3,000,000인 경우이다. 잭이 6,000,000 달러 집, 질이 3,000,000 달러 집 두 개를 가져가면 두 사람은 공평하게 집을 나눌 수 있다. 남는 집 (11,000,000 달러, 30,000,000 달러) 의 합은 41,000,000 달러이다.
출처
Contest > Waterloo's local Programming Contests > 26 Septemeber, 2010 C번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호