문제 탐색하기
입력 자료 정리
- n은 설치된 휴게소 개수, m은 설치할 휴게소 개수, l은 고속도로의 최대 길이다
- 이어서 들어오는 n개의 입력값은 이미 설치된 휴게소다
해결방법 추론
- 문제를 보자마자 이분탐색으로 푸는 문제라고 생각하기는 했는데...
입력값이 너무 작아서 브루트 포스로도 가능하지 않을까 생각했다 - 브루트 포스로 가능한 방법을 생각해봤는데, m개의 휴게소를 l개의 고속도로에 설치할 때 경우의 수를 모두 고려하면 될 것이다
- 하지만 해당 방법은 1000^100이라는 시간복잡도가 발생하기 때문에, 선택할 수 없다
- 따라서 브루트포스로는 불가능하고 다른 방법으로 해결해야겠다고 생각했다
- 휴게소가 없는 구간의 최댓값의 최솟값을 구하는 문제다.
조금 말장난 같은데 정리하면 추가로 설치하는 휴게소를 모두 설치했을 때 휴게소간 차이를 구하고
그 구간 중에 최댓값을 구하는 것이다. - 그리고 가능한 모든 경우의 수를 확인한뒤, 그 최댓값들 중에서 최솟값을 구하면 된다
- 그렇다면 문제를 어떻게 해결할 수 있을까? 조금 편하게 풀려면 휴게소간 차이를 구한 다음
각 차이마다 휴게소가 없는 구간의 최댓값 간격으로 설치한 다음 가능한 개수를 구하면 될것이다 - 그리고 그 개수를 기준으로 최댓값 간격을 조절하면 될 것이다!
- 이때 이분탐색을 이용해서 최댓값 간격을 log단위로 조절하면 문제를 해결할 수 있을 것이다
- 해결방법의 틀은 나왔고, 이 문제에서 주의할 점이 몇가지 있어 미리 정리했다
- 이미 설치된 휴게소 끼리의 간격만 구하면 안된다. 0번 지점과 가장 가까운 휴게소간의 차이,
l번 지점과의 가장 먼 휴게소간의 차이도 계산해야한다 - 이분탐색의 범위는 휴게소를 설치할 수 있는 위치로 판단한다. 따라서 1~l-1범위로 지정해야한다
- 두 지점의 차이는 휴게소를 설치할 수 있는 계산해야한다. 즉, 차이를 계산하는 두 지점은 제외한다 (0번 지점과 5번 지점에 설치되면 1,2,3,4만 설치할 수 있다.)
- 이제 주의점을 생각하고 추론한 방법으로 구현하면 된다!
시간복잡도 계산
- 이분탐색의 시간복잡도는 log l이다.
- 이때 이분탐색마다 모든 휴게소 간격을 확인하며 가능한 개수를 파악하므로 n의 연산이 추가로 발생한다
- 따라서 시간복잡도는 O(n x log l)이 되며 시간제한안에 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리
- 각 크기는 변수로 관리하며, n의 값들은 int형 1차원 배열로 관리한다
- n의 값을 보관하는 배열은 n+2의 크기로 선언한다. 고속도로의 시작과 끝도 보관하기 위함이다.
- 0번 인덱스와 n+1번 인덱스에 0과 l을 넣고, 차이를 계산하기 위해 오름차순 정렬을 한다
- 배열간 차이만 구해도 되긴 하는데, 조금더 편하게 하기 위해 차이를 관리할 리스트를 선언했다
- 해당 리스트에 두 배열간 차이 - 1을 넣어준다.
- 이분탐색을 위한 left와 right를 각각 1과 l-1로 선언한다
- 또한 정답을 위한 ans배열을 Integer.MAX_VALUE로 선언한다. 최솟값을 구하기 위함이다
구현 코드 설계
- 이분탐색을 시작한다. count 변수를 0으로 초기화해서 선언한다
- 모든 차이를 탐색하며, mid로 나눈 몫을 count에 더한다
- count와 m을 비교해서 만약 m보다 count가 큰 경우 left의 범위를 조절한다
너무 크기가 작아서 휴게소 사이에 많이 설치할 수 있기 때문이다. - 또한 3번의 경우는 정답으로 체크하지 않는다. m개만큼 설치하라고 했기 때문에 정답으로 선정할 수 없다
- 만약 3번이 아닌 경우 right의 범위를 조절해서 최적의 정답을 탐색한다
- 이때는 정답과 mid를 비교해서 더 작은 값으로 갱신한다
- 5번에서 count가 m보다 작은 경우도 포함되는데, m개만큼 설치되지는 않았지만 최댓값보다 작은 간격으로 설치가 가능하며 이 경우 정답에 변동을 주지 않기 때문이다
출력값 설계
- 완성한 ans를 출력하면 정답이 된다.
정답 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(st.nextToken());
int[] arr = new int[n+2];
arr[0] = 0;
arr[n+1] = l;
st = new StringTokenizer(br.readLine());
for (int i = 1; i < n+1; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
List<Integer> lists = new ArrayList<>();
for (int i = 1; i < n+2; i++) {
lists.add(arr[i] - arr[i-1]-1);
}
int left = 1;
int right = l-1;
int ans = Integer.MAX_VALUE;
while(left <= right){
int mid = (left + right)/ 2;
int count = 0;
for (int i = 0; i < n+1; i++) {
count += lists.get(i) / mid;
}
if(count > m){
left = mid + 1;
}else{
right = mid - 1;
ans = Math.min(ans, mid);
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}문제 링크
Software Developer