풀이 방법
집의 좌표가 0~1000000000까지라서 이분탐색을 이용해서 풀이해야겠다는 생각이 들었는데 접근하기가 어려웠다.
거리를 이분탐색해서 구했는데 사이 거리의 최솟값과 최댓값을 구해서 그 거리에 맞게 넣어주고 만족하는 최대거리를 찾아주었다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int N, C;
static ArrayList<Integer> list = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
int min = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
list.add(Integer.parseInt(br.readLine()));
if (i > 0)
min = Math.min(list.get(i) - list.get(i - 1), min);
}
Collections.sort(list);
int left = min;
int right = list.get(N - 1) - list.get(0);
int mid = 0;
int cnt = 0;
int answer = 0;
while (left <= right) {
mid = (right + left) / 2;
cnt = 1;
int temp = list.get(0);
for (int i = 1; i < N; i++) {
if (list.get(i) - temp >= mid) {
cnt++;
temp = list.get(i);
}
}
if (cnt >= C) {
left = mid + 1;
answer = Math.max(mid, answer);
} else {
right = mid - 1;
}
}
System.out.println(answer);
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
신입 사원 - 1946번 (0) | 2021.12.02 |
---|---|
암호코드 - 2011번 (0) | 2021.12.01 |
램프 - 1034번 (0) | 2021.11.26 |
감소하는 수 - 1038번 (0) | 2021.11.25 |
리모컨 - 1107번 (0) | 2021.11.23 |