20917번 - 사회적 거리 두기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 341 | 203 | 159 | 59.108% |
문제
Albert는 L대학에서 주최하는 Hackathon 행사 진행을 도와주기로 했는데, 사회적 거리 두기 방침에 따라 모든 참가자들을 최대한 멀리 떨어트려 좌석 배정을 해주려 한다. 이를 위해 아주 길다란 복도를 따라 특정 위치에 모니터, 책상, 의자를 두는 식으로 좌석을 배정하고, 각 좌석에는 최대 한 팀만 착석할 수 있다. 총 s개의 팀이 행사에 참가하고, 복도를 따라 총 n곳에 전원 공급이 가능한 콘센트가 설치되어 있다 -- 좌석은 반드시 콘센트가 설치된 곳에만 할 수 있다. 편의상 콘센트가 설치된 지점들의 위치를 x[1], x[2], ..., x[n] 이라 하자 (각 x[i]는 복도 입구로 부터의 거리를 나타낸다). 즉, i번째 콘센트는 복도의 입구로부터 x[i] 만큼 떨어진 곳에 있다.
Albert는 n개의 콘센트 위치 중 s개를 선택하여 좌석을 선택하되, 가장 가까운 두 좌석의 거리 (D라 하자)가 최대가 되도록 하고 싶다.
예를 들어, n = 3, s = 3 이고 x = [10, 100, 200]이라 하자. 이 경우 n = s 이므로 각 콘센트 위치에 좌석을 설치해야 한다. 가장 가까운 두 좌석의 거리는 (100 - 10) = 90 이다. 다른 예로, n = 6, s = 4 이고 x = [11, 19, 24, 26, 29, 30]이라 하자. 이 경우, x[1] = 11, x[2] = 19, x[3] = 24, x[4] = 29 각각에 좌석을 설치하면 가장 가까운 두 좌석의 거리는 5가 된다. 혹은, x[1] = 11, x[2] = 19, x[3] = 24, x[4] = 30을 선택하는 것도 가능하다. 가장 가까운 두 좌석의 거리가 6 이상이 되도록 4개의 좌석을 설치하는 방법은 없다.
입력으로 n, s, 그리고 x[1], ..., x[n]이 주어지면 가능한 가장 큰 D값을 출력하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 두 줄에 걸쳐 주어진다.
첫 줄에 n과 s가 공백으로 구분되어 주어진다. 다음 줄에 설치된 콘센트의 위치를 나타내는 n개의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스에 대해 달성 가능한 최대 D값을 출력한다.
제한
- 1 ≤ T ≤ 10
- 2 ≤ s ≤ n ≤ 200,000
- 1 ≤ x[i] ≤ 1,000,000,000
- x[i]값은 중복되지 않는다.
예제 입력 1
3 3 3 10 100 200 7 3 28 11 17 19 21 22 23 6 4 11 19 24 26 29 30
예제 출력 1
90 8 5
케이스 1: 본문에서 다루었다.
케이스 2: [11, 19, 28]을 선택하면 D = 8이 된다.
케이스 3: 본문에서 다루었다.
시간 제한
- Python 3: 14 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호