문제 링크
문제
티어: 골드 1
알고리즘: 그리디, 이분탐색, 매개 변수 탐색
벌목꾼 백은진은 나무를 종이 공장에 옮겨야 한다. 하지만, 통나무의 길이가 너무 길어서 트럭에 들어가지 않으므로, 여러개의 조각으로 나누려고 한다.
통나무의 길이는 L이고, K개의 위치에서만 자를 수 있다. 통나무를 자를 수 있는 위치가 주어진다. 이 위치는 통나무의 가장 왼쪽에서부터 떨어진 거리이다. 통나무를 자를 수 있는 횟수는 최대 C번이다.
통나무의 가장 긴 조각을 작게 만들고, 그 길이를 구해보자.
입력
첫째 줄에 세 정수 L, K, C가 주어진다. 둘째 줄에는 통나무를 자를 수 있는 위치가 주어진다.
출력
첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출력한다.
제한
- 2 ≤ L ≤ 1,000,000,000
- 1 ≤ K, C ≤ 10,000
- 1 ≤ 자를 수 있는 위치 ≤ L
풀이
통나무의 가장 긴 조각을 작게 만들고, 그러한 경우가 여러 가지라면, 처음 자르는 위치가 작은 것을 출력해야 한다.
가장 긴 조각을 작게 만들기 위해서는 이분 탐색을 활용할 수 있다. max L에서 중간값을 설정하고, 설정해 준 max 값이 되게끔 통나무를 잘라 보는 것이다.
어떻게 자르는 것이 최선의 결과를 만들어 낼까?
통나무를 잘랐을 때 설정해 준 max보다 작거나 같은 것은 당연하지만, 최대한 수렴하게끔 자른다면, 자르는 횟수를 최소로 할 수 있기 때문에 max와 최대한 수렴하게끔 자르는 것이 최선이 된다.
그런데 중요한 점은 처음 자르는 위치를 최대한 왼쪽으로 땡겨줘야 한다는 것이다.
그렇게 하기 위해서 첫 번째 자를 때 최대한 수렴하게 자르는 것이 오히려 답이 될 수 없는 모순이 생긴다.
그러면 이렇게 생각해 보자, 최대한 max와 수렴하게 잘랐을 때 마지막 구간이 max보다 한참 적다고 생각해 보는 것이다. 그러면 자연스럽게 그 뒤 구간을 포함하는 방식을 생각할 수 있고, 결국 뒤에서부터 max와 최대한 수렴하게끔 자르는 것이 최선이라는 것을 알 수 있다.
그리고, 자르는 횟수가 남았다면, 가장 왼쪽 자르는 위치가 정답이 된다. 왜냐하면 잘라놓은 모든 통나무가 max보다 작거나 같을 때 통나무를 더 자른다고 해서 max가 커지지 않기 때문이다.
이 문제에서 주의할 점은 자르는 위치가 중복으로 나올 수 있다는 점과 정렬되어 있지 않다는 것이다. 이를 주의하자.
이 풀이의 시간 복잡도는 O(logL x K)가 된다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int L, K, C, answer;
static int fc = -1;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
HashMap<Integer, Boolean> visited = new HashMap<>();
ArrayList<Integer> list = new ArrayList<>();
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i=0; i<K ;i++) {
int num = Integer.parseInt(st2.nextToken());
if(visited.get(num) == null) {
visited.put(num, true);
list.add(num);
}
}
Collections.sort(list);
binarySearch(list);
System.out.println(answer + " " + (list.get(fc)));
}
static void binarySearch(ArrayList<Integer> list) {
int min = 1;
int max = L;
while(min <= max) {
int mid = (min + max) / 2;
int result = isPosible(mid, list); //-1이면 불가능
if(result != -1) {
//가능한 경우라면
fc = result;
max = mid - 1;
} else {
//불가능한 경우라면
min = mid + 1;
}
}
answer = min;
}
static int isPosible(int maxLen, ArrayList<Integer> list) {
int result = -1; // first cut index
//가장 오른쪽에서부터 잘라나간다.
int end = L;//통나무 끝
int endIndex = list.size(); //통나무 끝 인덱스
int cnt = 0; //자른 횟수
int cursor = list.size() - 1;
while(cursor >= 0) {
if(end - list.get(cursor) <= maxLen) {
cursor -= 1;
} else {
//end - list.get(cursor) > maxLen 라면 잘라줘야 될 위치는 cursor + 1
if(cursor + 1 >= endIndex) {
//잘라줘야 될 위치가 통나무 끝을 포함해서 벗어난다면 불가능한 경우임
return -1;
} else {
//최선으로 잘라줄 수 있는 위치임
if(cnt + 1 > C) {
//전체 자를 수 있는 횟수를 넘는다면 불가능함.
return -1;
}
//횟수도 가능한 경우 잘라준다.
cnt += 1;
end = list.get(cursor + 1);
endIndex = cursor + 1;
}
}
}
//여기까지 왔다면 cursor = -1를 가지고 있음
if(cnt == C) {
//더 이상 자를 수 없다면
if(end > maxLen) {
return -1;
}
//end <= max
result = endIndex; //가장 첫 번째로 자른 위치는 endIndex임
} else {
//더 자를 수 있음.
end = list.get(0);
endIndex = 0;
if(end > maxLen) {
return -1;
}
//end <= max
result = endIndex;
}
return result;
}
}