[백준] Gold IV. 케이크 자르기
https://www.acmicpc.net/problem/17179
문제
생일을 맞이한 주성이가 생일 파티를 준비하려고 한다. 주성이는 일반 케이크 대신 평소 좋아하던 롤 케이크를 준비했다. 롤 케이크에는 장식이 존재해서 특정 위치에서만 자를 수 있다. 주성이는 롤 케이크 조각을 파티에 올 친구의 수 만큼 준비하고 싶어서, 가장 작은 조각의 크기를 미리 알아보기로 했다. 하지만 짓궂은 주성이의 친구들은 생일파티에 몇 명이 참석하는지 직접적으로 알려주지를 않는다. 그래서 몇 개의 수를 목록에 적어, 각 수만큼 조각을 만들었을 때 가장 작은 조각의 길이의 최댓값을 구하려고 한다.
예를 들어 70cm의 롤 케이크에 자를 수 있는 지점이 5군데(10cm, 20cm, 35cm, 55cm, 60cm)가 있다고 하자. 만약 목록에 적힌 수 중 하나가 3이라면 이때 가장 작은 조각의 길이는 최대 15cm이다. 예를 들어 20cm, 35cm, 55cm 지점을 자를 때 최대가 된다.
입력
첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000)
다음 M줄에 걸쳐 자를 수 있는 지점을 나타내는 정수 Si가 주어진다. (1 ≤ Si < L)
다음 N줄에 걸쳐 자르는 횟수를 나타내는 정수 Qi가 주어진다. (1 ≤ Qi ≤ M)
Si는 오름차순으로 주어지고 중복되는 수는 없으며, Qi도 마찬가지이다.
출력
N개 줄에 걸쳐 각 목록에 있는 횟수대로 롤 케이크를 잘랐을 때 가장 작은 조각의 길이의 최댓값을 출력한다.
알고리즘
- 이분 탐색
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class boj17179 {
static int n, m, l;
static int [] area;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
l = Integer.parseInt(st.nextToken());
area = new int[m+1];
for(int i = 0; i < m; i++) {
area[i] = Integer.parseInt(br.readLine());
}
area[m] = l;
for(int i = 0; i < n; i++) {
int count = Integer.parseInt(br.readLine());
int lo = 1; int hi = l; // 1 70, mid = 35
int ans = 0;
while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid, count)) {
lo = mid + 1;
ans = Math.max(ans, mid);
}
else {
hi = mid - 1;
}
}
System.out.println(ans);
}
}
public static boolean check(int mid, int k) {
int prev = 0;
for(int num : area) {
if (num - prev >= mid) {
k--;
prev = num;
}
}
if (k < 0) return true;
return false;
}
}
회고
풀어봤던 이분 탐색 중에서 제일 헷갈리는 문제였다. mid값에 대해 어떻게 이해하는지 시간이 오래걸렸다.
(10cm, 20cm, 35cm, 55cm, 60cm) 문제에서 이렇게 예시가 있고, 길이가 70이기 때문에 배열의 마지막 index에 70을 넣어준다.
그리고, 이분탐색의 시작점은 1, 끝점은 길이인 l로 고정한다. mid 값은, 자를수 있는 가장 작은 조각의 단위로 이제 이 값을 이용해서 count와 비교를 해줘야한다.
check() 메서드는 다음과 같이 동작한다.
[10, 20, 35, 55, 60, 70] 이렇게 있을 때, 처음부터 배열을 순회하면서 현재 값에서 prev를 뺀 값이 mid 이상인지 체크한다.
mid값은 (1 + 70)/ 2 = 35이므로, 차이가 mid 이상이 되는 지점은 35이다.
| 10 | 20 | 35 | 55 | 60 | 70 |
k를 1 감소시켜주고, prev를 현재 위치인 35로 고정한다. 다시 배열을 순회하면서 값의 차이를 계산해보면,
num = 35
num - prev = 35
num = 55
num - prev = 20
num = 60
num - prev = 25
num = 70
num - prev = 35
마지막 70에 와서야 mid값 이상으로 자를 수 있다는 의미가 된다.
결국, 길이가 70을 35로 자른다고 했을 때 롤 케이크를 두개로 자를 수 있다. 하지만 문제에서 주어진 자를 수 있는 지점은 3개이기 때문에, 35라는 값은 적절한 값이 될 수 없다.
mid값을 낮춰서 케이크를 더 많이 자를수 있게 해주어야 하는데, 그렇다면 상한점을 낮춰줘야한다.
이렇게 상한점을 낮춰주다가, k가 0보다 작은 경우는 문제에서 주어진 지점 갯수 이상으로 자를 수 있다는 의미이므로 얘네 중에서 mid값의 최댓값을 구하면 된다.