danbibibi
article thumbnail

1. 문제

문제 바로가기> BOJ 2110번: 공유기 설치

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

 

2. 풀이

<cpp />
#include<iostream> #include<algorithm> #define INF 1000000001 #define MAX_HOME 200001 using namespace std; int N, C; int home[MAX_HOME]; void input() { cin >> N >> C; for (int i = 0; i < N; i++) cin >> home[i]; sort(home + 0, home + N); // 정렬 } bool check(int len) { int before=home[0], cnt=1; // 기준, 공유기 개수 for (int i = 1; i < N; i++) { if (len <= home[i] - before) { before = home[i]; cnt++; } } if (cnt < C) return false; return true; } void solution() { // 가장 인접한 두 공유기 사이의 최대 거리 int low = 0, high = INF; while (low <= high) { int mid = (low + high) / 2; if (check(mid)) low = mid + 1; // 더 넓게 공유기를 설치할 수 있는 경우 else high = mid - 1; // 공유기를 더 좁게 설치해야 하는 경우 } cout << high; // 가장 인접한 두 공유기 사이의 최대 거리 } int main() { ios_base::sync_with_stdio(0); cin.tie(0); input(); solution(); }

'문제 풀이 > 백준' 카테고리의 다른 글

BOJ16946번: 벽 부수고 이동하기 4  (0) 2023.02.25
BOJ 17471번: 게리맨더링  (0) 2023.02.23
BOJ 2343번: 기타 레슨  (0) 2023.02.23
BOJ 6987번: 월드컵  (0) 2023.02.22
BOJ 16974번: 레벨 햄버거  (0) 2023.02.21
profile

danbibibi

@danbibibi

꿈을 꾸는 시간은 멈춰 있는 것이 아냐 두려워하지 마 멈추지 마 푸른 꿈속으로