Baekjoon2110: 공유기 설치

Baekjoon2110: 공유기 설치

공유기 설치

2 초 128 MB 30853 11897 8441 39.544%

문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. 출력 첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

풀이

만족하는 값 중 최대값을 구하라 → Upper Bound를 구해야한다

N개의 위치값을 먼저 정렬하면 arr[0]~arr[N-1] 의 수가 정렬된다.

공유기 사이 거리의 최소값은 1부터 arr[N-1]-arr[0] 까지 가능하고

Upper Bound이므로 끝 값에 1을 더해준다. 즉, arr[N-1]-arr[0]+1이 최대값이다.

공유기 설치

최소값과 최대값을 통해 mid값을 구하고 이 거리값으로 공유기의 설치를 하나씩 하면서 몇 개를 설치할 수 있는지 구한다

설치할 수 있는 개수가 C보다 같거나 크면 공유기 사이의 거리가 이보다 넓어질 수 있다는 의미이다 → min=mid+1

C보다 작으면 거리를 좁혀서 더 많은 공유기를 설치해야한다는 뜻이다 → max = mid 이다 (Upper Bound 식)

결과값

설치할 수 있는 개수가 C 보다 많아지는 최소의 길이가 구해진다 여기서 -1을 하는 순간

C개를 설치할 수 있는 최대의 길이를 구할 수 있다 (Upper Bound)

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int C = sc.nextInt(); int[] arr = new int[N]; for(int i=0;i=start+mid) { count++; start=arr[i]; } } if(count>=C) { min=mid+1; }else { max=mid; } } System.out.print(min-1); }}

from http://devyoseph.tistory.com/189 by ccl(A) rewrite - 2021-12-20 23:27:20