https://www.acmicpc.net/problem/1477
다솜이는 고속도로에 휴게소 N개를 갖고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 휴게소 M개를 더 세워서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. 조건은 아래와 같다.
- 다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다.
- 고속도로의 끝에도 휴게소를 세울 수 없고, 휴게소는 정수 위치에만 세울 수 있다.
- 반드시 M개의 휴게소를 모두 지어야 한다.
휴게소에 대한 정보가 주어질 때, M개의 휴게소를 짓고 난 후 휴게소가 없는 구간의 최댓값의 최솟값을 구하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 0 ≤ N ≤ 50
- 1 ≤ M ≤ 100
- 100 ≤ L ≤ 1,000
- 1 ≤ 휴게소의 위치 ≤ L-1
- N+M<L
- 모든 휴게소의 위치는 중복되지 않는다.
- 입력으로 주어지는 모든 수는 정수다.
휴게소가 없는 구간의 최댓값을 매개 변수로 두고, 조건에 맞는 최솟값을 이분탐색을 적용해 찾아야 한다. left는 휴게소 위치의 최솟값인 1로, right는 고속도로의 길이에서 1을 뺀 값으로 둔다.
휴게소 간격마다 조건에 맞춰 휴게소를 추가로 설치한 뒤, 총 설치한 개수가 조건에 맞는지 확인해야 한다. m보다 작거나 같은 경우 조건을 만족하는 것으로 보고 정답을 갱신하고, 정답들 중 최솟값을 구하기 위해 right를 줄이면 된다. 조건을 만족하지 않는다면 left를 늘려 휴게소를 더 적게 설치하도록 해야 한다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- N, M, L, 휴게소 위치 정보 입력받기
- 휴게소 위치 배열 정렬하기
- 휴게소가 없는 구간의 최댓값을 매개 변수로 놓고 이분탐색 진행하기
- 고속도로의 휴게소 간격마다 mid 값에 맞춰 휴게소 설치하고 개수 저장하기
- 설치한 개수가 m보다 작거나 같으면 mn 값 갱신하고 right 줄이기
- 설치한 개수가 m보다 크면 left 늘리기
- mn 값 출력
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
1~3회차
- mn 값을 갱신할 때, 설치한 휴게소 개수와 m이 같을 때만 갱신하는 조건문을 없애야 함
- l은 1로, r은 L-1로 초기화해야 함
정답 코드
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,L,arr[52];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> L;
arr[0] = 0;
arr[n+1] = L;
for (int i=1; i<=n; i++) cin >> arr[i];
sort(arr,arr+n+1);
int l=1,r=L-1,mn=L;
while (l<=r) {
int mid=(l+r)/2,tmp_m=0;
for (int i=0; i<n+1; i++) {
int tmp = arr[i+1] - arr[i];
if (tmp>=mid) {
tmp_m += (tmp%mid==0 ? tmp/mid-1 : tmp/mid);
}
}
if (tmp_m<=m) {
mn = min(mn,mid);
r = mid-1;
}
else {
l = mid+1;
}
}
cout << mn;
}