728x90
반응형
▷ 문제
N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.
현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고,
가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.
* 입력
첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.
둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.
* 출력
첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.
▷ 입력 예시
5 3
1 2 8 4 9
▷ 출력 예시
3
▷ 풀이
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public int count(int[] arr, int dist){
int cnt = 1;
int ep = arr[0];
for(int i=1; i<arr.length; i++){
if(arr[i]-ep >= dist){
cnt++;
ep = arr[i];
}
}
return cnt;
}
public int solution(int n, int m, int[] arr){
Arrays.sort(arr);
int answer = 0;
int lt = 1;
int rt = arr[n-1];
while(lt <= rt){
int mid = (lt + rt) / 2;
if(count(arr, mid) >= m){
answer = mid;
lt = mid + 1;
} else{
rt = mid - 1;
}
}
return answer;
}
public static void main(String[] args){
Main main = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = kb.nextInt();
}
kb.close();
System.out.println(main.solution(n, m, arr));
}
}
▷ 메모
- 결정알고리즘은 이분탐색을 사용하며 이분탐색은 정렬 후 수행해야 함을 주의
- 첫 말은 첫 번째 마구간에 넣어야 하므로 lt는 1로 초기화한다.
반응형
'Algorithm > Sorting and Searching' 카테고리의 다른 글
[알고리즘 문제]뮤직비디오 - 결정알고리즘 (0) | 2021.11.03 |
---|---|
[알고리즘 문제]이분검색 (0) | 2021.11.02 |
[알고리즘 문제]장난꾸러기 (1) | 2021.10.30 |
[알고리즘 문제]중복 확인 (0) | 2021.10.30 |
[알고리즘 문제]LRU 알고리즘 - Cache Miss, Cache Hit (0) | 2021.10.30 |