16286번 - Panokseon 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 254 | 75 | 60 | 28.846% |
문제
이순신 장군은 판옥선이라 불리는 특별한 전함을 전쟁에 대비해 만들었다. 판옥선의 성능을 평가하기 위해, 조선 수병들로 하여금 경주를 하도록 할 계획이다. n 명의 수군들을 1 번부터 n번까지 차례로 번호를 매긴 후, 각 전함에 연속된 번호의 수군들의 몸무게의 합이 전함의 중량 한계 W를 넘지 않도록 배정하려고 한다. 즉, 한 전함에 배정된 수군들은 연속된 번호를 가져야하며, 그들의 몸무게 합이 W 이하여야 한다. 충분히 많은 전함을 준비했기 때문에, 한 명 이상의 수군이 배정된 전함의 수는 중요하지 않고, 경주의 공정성, 즉 배정의 공정성이 더 중요하다. 이순신 장군은 전함 별 수군들의 몸무게 합의 차이가 작을수록 더 공정한 배정이라고 판단하였다.
보다 명확히 설명하면 다음과 같다. 한 명 이상의 수군이 배정된 전함의 여유중량 (emptiness) 값은 W와 그 전함에 배정된 수군들의 몸무게 합의 차이를 제곱한 값으로 정의한다. 배정의 불공정성 (unfairness) 값은 배정에 사용된 군함의 여유중량 값들 중에서 최댓값으로 정의한다. 이순신 장군은 불공정성이 가장 작은 배정이 가장 공정한 배정이라고 생각했다.
예를 들어, 3 명의 수군의 몸무게가 차례대로 10, 20, 30이고, W = 50 인 경우를 고려해보자. 가능한 배정 중 하나인 {[1],[2],[3]} 은 하나의 전함에 수군을 한 명씩 배정하는 것이다. 이 배정의 불공정성은 max{(50 − 10)2, (50 − 20)2, (50 − 30)2} = 1600이다. 다른 두 가지 배정 {[1, 2],[3]}과 {[1],[2, 3]} 도 가능한데, 두 배정의 불공정성은 각각 max{(50 − 30)2, (50 − 30)2} = 400 과 max{(50 − 10)2, (50 − 50)2} = 1600이 된다. 그러나 3 명의 수군들의 몸무게 합이 W = 50보다 크기 때문에 모두 한 전함에 배정할 수는 없다. 따라서, 불공정성의 최소 값은 400이 되어 {[1, 2],[3]}이 가장 공정한 배정이 된다. 이 배정은 1번, 2번 수군을 같은 전함에, 3번 수군은 다른 전함에 배정하는 것이다.
여러분은 전함의 한계 중량 W와 1번부터 n번 수군까지 몸무게가 차례로 주어질 때, 가장 공정한 배정을 찾는 프로그램을 작성해야 한다.
입력
입력은 표준입력을 사용한다. 첫 번째 줄에는 전함의 한계 중량 W (1 ≤ W ≤ 109)와 수군의 수 n (1 ≤ n ≤ 500,000)이 공백을 사이에 두고 차례로 주어진다. 두 번째 줄에는 수군의 몸무게가 1번 수군부터 n번 수군의 순서로 차례로 주어진다. 수군 몸무게는 1 이상 W 이하의 정수이다. 수군 한 명의 몸무게는 W보다 크지 않다.
출력
출력은 표준출력을 사용한다. 주어진 입력에 대한 배정의 불공정성의 최소 값을 한 줄에 출력한다.
예제 입력 1
50 3 10 20 30
예제 출력 1
400
예제 입력 2
5 4 1 3 1 3
예제 출력 2
1
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호