반응형
https://www.acmicpc.net/problem/2110
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
[ 문제풀이 ]
1. 공유기의 위치를 입력받고, 배열을 오름차순으로 정렬합니다.
2. 공유기의 간격이 최소 0에서 최대 1,000,000,000이므로 left = 0, right = 1,000,000,001로 설정하고, 이분 탐색을 진행해줍니다.
3. mid = (left + right) / 2로 설정하고, 0번 째 공유기를 기준으로 해당 mid 값보다 더 떨어져 있는 공유기가 있다면 cnt++를 해주고, 기준을 해당 공유기로 바꿔줍니다. 이를 반복하며 cnt가 C보다 크거나 같다면 left = mid + 1이 되고, 그렇지 않다면 right = mid가 됩니다.
4. mid 값 중 가장 큰 값을 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include<iostream> #include<algorithm> using namespace std; int N, C; int arr[200000]; bool check(int mid) { int base = arr[0]; int cnt = 1; for (int i = 1; i < N; i++) { if (arr[i] - base >= mid) { base = arr[i]; cnt++; } if (cnt >= C) return true; } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> C; for (int i = 0; i < N; i++) { cin >> arr[i]; } sort(arr, arr + N); int left = 0; int right = 1000000001; int ans = 0; while (left < right) { int mid = (left + right) / 2; if (check(mid)) { left = mid + 1; ans = max(ans, mid); } else { right = mid; } } cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2295번 - 세 수의 합 (C++) (0) | 2023.07.14 |
|---|---|
| [ 백준 ] 1477번 - 휴게소 세우기 (C++) (0) | 2023.07.13 |
| [ 백준 ] 10866번 - 덱 (C++) (0) | 2023.07.11 |
| [ 백준 ] 3151번 - 합이 0 (C++) (0) | 2023.07.10 |
| [ 백준 ] 5430번 - AC (C++) (0) | 2023.07.09 |