문제
생일을 맞이한 주성이가 생일 파티를 준비하려고 한다. 주성이는 일반 케이크 대신 평소 좋아하던 롤 케이크를 준비했다. 롤 케이크에는 장식이 존재해서 특정 위치에서만 자를 수 있다. 주성이는 롤 케이크 조각을 파티에 올 친구의 수 만큼 준비하고 싶어서, 가장 작은 조각의 크기를 미리 알아보기로 했다. 하지만 짓궂은 주성이의 친구들은 생일파티에 몇 명이 참석하는지 직접적으로 알려주지를 않는다. 그래서 몇 개의 수를 목록에 적어, 각 수만큼 조각을 만들었을 때 가장 작은 조각의 길이의 최댓값을 구하려고 한다.
예를 들어 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개 줄에 걸쳐 각 목록에 있는 횟수대로 롤 케이크를 잘랐을 때 가장 작은 조각의 길이의 최댓값을 출력한다.
예제 입력 1
2 5 70
10
20
35
55
60
3
4예제 출력 1
15
10문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ17179 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
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[] loc=new int[M+1];
for(int i=0;i<M;i++){
loc[i]=Integer.parseInt(br.readLine());
}
loc[M]=L;
for(int i=0;i<N;i++){
int num=Integer.parseInt(br.readLine());
int answer=0;
int left=0;
int right=loc[M-1];
while(left<=right){
// 가장 작은 조각 길이
int mid=(left+right)/2;
int cnt=0;
int prev=0;
for(int idx=0;idx<=M;idx++){
if(loc[idx]-prev>=mid){
cnt++;
prev=loc[idx];
}
}
if(cnt>num){
left=mid+1;
answer=Math.max(answer,mid);
}
else{
right=mid-1;
}
}
System.out.println(right);
}
}
}이분탐색을 할 때는 어떤 값을 기준으로 하여 탐색을 진행할 것인지 판단해야한다.
문제를 읽어보면 롤 케이크를 잘랐을 때 가장 작은 길이의 최댓값을 구하는 것이다.
가장 작은 길이의 최대값이라는 것이 애매하지만 롤 케이크를 잘랐을 때의 길이를 기준으로 탐색을 진행하면 된다는 것을 판단할 수 있다.
이분탐색
int num=Integer.parseInt(br.readLine());
int answer=0;
int left=0;
int right=loc[M-1];
while(left<=right){
// 가장 작은 조각 길이
int mid=(left+right)/2;
int cnt=0;
int prev=0;
for(int idx=0;idx<=M;idx++){
if(loc[idx]-prev>=mid){
cnt++;
prev=loc[idx];
}
}
if(cnt>num){
left=mid+1;
answer=Math.max(answer,mid);
}
else{
right=mid-1;
}
}num 변수에 자르는 횟수를 넣어주고 자르는 횟수에 맞춰 자른 길이의 최솟값을 구한다.
이때 주의해야할 점은
- 자르는 구간이 정해져있다는 것
- 마지막에 자른 구간에서 케이크의 마지막 부분까지의 길이 또한 계산해야한다는 것
이다.
우선 mid 값에는 임시로 정한 케이크를 자른 최소의 길이를 넣어준다.
그리고 해당 길이가 최소값이 되도록 케이크를 잘랐을 때 num 횟수를 넘어간다면 mid 값을 크게 만들어주어 자르는 횟수를 줄인다
반대로 num 횟수를 넘어가지 못한다면 mid 값이 크다는 뜻이므로 작게 만들어주어 자르는 횟수를 늘린다
자른 횟수 계산하기
loc[M]=L;
...
int cnt=0;
int prev=0;
for(int idx=0;idx<=M;idx++){
if(loc[idx]-prev>=mid){
cnt++;
prev=loc[idx];
}
}최소의 길이가 정해져있는 상황에서 자른 횟수를 구하려면 자르는 지정 위치를 하나씩 탐색하고 이전에 자른 부분과의 길이차이가 mid 이상인 경우에만 자르도록 구현한다.
이때, 케이크의 마지막 부분과 마지막으로 자른 부분까지의 길이도 계산해야하므로 loc 배열의 마지막에 케이크의 길이를 넣어주고 마지막 길이도 계산한다.
mid 값이 최소길이이면 되기 때문에 mid 보다 큰 길이라면 자를 수 있다.
이분탐색을 위한 분기 설정
if(cnt>num){
left=mid+1;
answer=Math.max(answer,mid);
}
else{
right=mid-1;
}cnt에는 자른 횟수가 담겨있다.
원래는 cnt값이 num과 같을때에도 허용이 되지만 길이를 체크할 때 마지막 길이를 자른 횟수도 포함되어있으므로 if문에는 num보다 큰 경우에 조건을 만족했다고 판단한다.
이때, 최소길이의 최댓값을 구하는 것이므로 조건을 만족한다면 조금 더 길이를 늘려보기 위해 left의 범위를 높여주고 answer 값을 갱신한다.
반대의 경우에는 길이를 줄여야 하므로 right의 범위를 낮춰주어 탐색을 반복한다.
