https://www.acmicpc.net/problem/2110
각각의 집의 좌표가 x1, ..., xN인 집 N개가 수직선 위에 있다. 집에 공유기 C개를 설치하려고 하는데, 한 집에는 공유기를 하나만 설치할 수 있고 가장 인접한 두 공유기 사이의 거리를 가능한 크게 해 설치하려고 한다. 이때 가장 인접한 두 공유기 사이 거리의 최댓값을 구하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 2 ≤ N ≤ 200,000
- 2 ≤ C ≤ N
- 0 ≤ xi ≤ 1,000,000,000
이분탐색을 진행하기 위해 집의 좌표를 입력받고 오름차순으로 정렬해야 한다.
가장 인접한 두 공유기 사이 거리를 매개변수로 놓고 이분탐색을 진행해야 한다. 집 N개 중 공유기를 C개만 설치할 수 있기 때문에 백트래킹 등을 사용해 집을 먼저 구하고 거리를 구해야 할지 고민했지만 N이 200,000까지라 시간초과가 날 수 있기 때문에 늘 하던대로 반복문을 통해 조건에 맞는지 확인하는 방식을 사용했다.
이분탐색을 진행할 때, 첫 번째 집에는 무조건 공유기를 설치한다고 가정해야 한다. 이유는 아래와 같다.
- 첫 번째 집에 공유기를 설치하지 않는다고 가정하면 공유기를 설치한 나머지 집들의 거리 차는 D1, D2, ..., D(C-1)로 볼 수 있다. 이때 가장 왼쪽에 설치된 공유기를 첫 번째 집으로 옮기면 D1은 답이 아니게 된다. 따라서 첫 번째 집에 공유기가 설치돼야만 한다.
거의 똑같은 문제로 20917 - 사회적 거리 두기가 있다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- N, C, 집 좌표 입력받기
- 집 좌표 정렬하기
- 가장 인접한 두 공유기 사이의 거리를 매개변수로 놓고 이분탐색 진행
- l을 0으로, r을 집 좌표 중 최댓값으로 놓기
- sum은 0으로, cnt는 1로 선언(첫 번째 집에 이미 설치됐다고 가정)
- 반복문을 통해 지금 보고 있는 좌표와 최근 공유기를 설치한 곳의 좌표의 거리가 mid 이상이라면 해당 위치에 공유기 설치
- 최근 공유기를 설치한 좌표 & 공유기 설치 개수 갱신
- ans 출력
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
pass
정답 코드
#include <iostream>
#include <algorithm>
using namespace std;
long long int n,c,arr[200001],ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(); cout.tie();
cin >> n >> c;
for (int i=0; i<n; i++) cin >> arr[i];
sort(arr,arr+n);
int l=0,r=arr[n-1];
while (l<=r) {
long long int mid=(l+r)/2,sum=0,last=0,cnt=1;
for (int i=0; i<n; i++) {
sum = arr[i] - arr[last];
if (sum>=mid) {
last = i;
cnt++;
}
}
if (cnt>=c) {
l = mid+1;
ans = max(ans,mid);
}
else {
r = mid-1;
}
}
cout << ans;
}