[BOJ 2110] 공유기 설치 (java, 이진 탐색)알고리즘/이진탐색2023. 6. 3. 19:21
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/2110
풀이
매개변수 (paramatrix search) 탐색 문제 (그리디 포함)
문제 지문
C 개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 최대 거리(Dmax) 를 구하시오.
뒤집은 지문
두 공유기 사이의 거리 (D)를 라 할때, C개의 공유기를 설치 가능한가(yes/no)? 이때 설치 가능한 최대 거리(Dmax)는 얼마인가 ?
아래와 같이 변수 범위가 주어졌을 때
집의 개수 N (2 ≤ N ≤ 200,000)
공유기의 개수 C (2 ≤ C ≤ N)
집의 좌표 x (0 ≤ x ≤ 1,000,000,000)
1) 집의 개수 N 개에 대해 정렬 수행 : O(NlogN) = O(20만log20만)
2) 임의 거리 (D)에 대해 C개의 공유기를 설치가능 여부 확인 : O(N)
3) 거리가 0 ~ 10억일때 C개의 공유기를 설치가능한 최대 거리 찾기 위해 이진탐색 수행 : O(logX)
4) 총 시간 복잡도는 O(NlogN + NlogX) = O(20만log20만 + 20만log10억)
대략 10억 = 10^9 일때 2^30정도로 생각해서 연산한다면 최대 600만 정도 연산 수행하니 풀이 가능
제출 코드
import java.io.*;
import java.util.*;
public class BOJ2110 {
static int N, C;
static int[] houses;
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 집의 개수
C = Integer.parseInt(st.nextToken()); // 공유기 개수
houses = new int[N + 1];
for(int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
houses[i] = Integer.parseInt(st.nextToken());
}
}
/**
*그리드 기법 사용하여 정렬 후 제일 왼쪽(1번)집 기준으로 조건 만족하는지 조회 : O(N)
*
* D만큼 거리 차이를 둔다면 C개 만큼의 공유기를 설치할 수 있는가? yes/no
*/
static boolean isValidDistance(int D) {
int cnt = 1, last = houses[1];
for(int i = 2; i <= N; i++) {
if(houses[i] - last >= D) {
cnt += 1;
last = houses[i];
}
}
return cnt >= C;
}
static void pro() {
Arrays.sort(houses, 1, N + 1);
int result = 0;
int L = 0, R = 1000000000;
while(L <= R) {
int distance = (L + R) / 2;
if(isValidDistance(distance)) {
L = distance + 1;
result = distance;
} else {
R = distance - 1;
}
}
System.out.println(result);
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
어려웠던 점
그리디 알고리즘을 생각하지 못해서 1번 집부터 연산하지 못 해 시간 소비했음
반응형
'알고리즘 > 이진탐색' 카테고리의 다른 글
[BOJ 6236] 용돈 관리 (Java, 매개변수 탐색) (0) | 2023.06.05 |
---|---|
[BOJ 2343] 기타 레슨 (Java, 매개변수 탐색) (0) | 2023.06.05 |
[BOJ 1300] K번째 수 (Java, 이진탐색) (0) | 2023.06.03 |
[BOJ 1654] 랜선자르기 (java, 이진탐색) (1) | 2023.06.03 |
[BOJ 2470] 두 용액 (java, 이진탐색) (0) | 2023.06.03 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!