[백준] 17179번 - 케이크 자르기 (Java)

 

https://www.acmicpc.net/problem/17179

17179번: 케이크 자르기

 

<문제 분석>
N : 자르는 횟수 ( <= 1,000)
M : 자를 수 있는 지점의 개수 ( <= 1,000)
L : 롤 케이크의 길이 (<= 4,000,000)
for(i to M)
S[i] : 자를 수 있는 지점 - 인덱스
for(i to N)
Q[i] : 자르는 횟수
오름차순으로 주어짐 - 상한선 구할 필요 없음.

Q[i]의 횟수대로 롤케이크를 잘랐을 때 가장 작은 조각의 길이의 최대값 출력

 

<풀이>

1. mid 값 정하기(중요)
mid : 가장 작은 조각의 길이
start : 0
end : L (롤케이크의 길이)
key값 : 자르는 횟수 Q[i]
arr[mid]값 : cutCake(mid)의 결과값

2. cutCake 함수 정의
for ( i to M) {
  // 케이크의 자른 조각의 길이는 무조건 mid보다 커야 한다.
  // 왜냐하면 mid는 가장 작은 조각의 길이이기 때문이다.
  if (S[i] - prev(이전에 자른 위치) >= mid) {
    prev = S[i]; // 지금 자른 위치를 다음 비교를 위해 저장
count++; // 자른 횟수 증가
}
return count;
}

3. 이분 탐색 조건 최적화
// mid값이 커질수록 count값은 감소한다
if (count > key) { // 자른 개수가 많으니까 하한선을 올린다. 
  start = mid + 1;
  } else if (count == key) { // 자른 개수가 일치한다. 중복 값들 중 가장 큰 값을 골라야 함.
  start = mid + 1;
  ans = Math.max(ans, mid); // 최대값을 계속 저장해 나간다
  } else { // 자른 개수가 적으니까 상한선을 내린다.
  end = mid - 1;

 

※ 이렇게 구현 했을 때 결과가 원하는 값이 나오질 않았다. 로그를 추가해가면 확인을 했는데 cutCake()의 count값이 이상한 것을 발견했다. mid(최소 조각 길이)보다 같거나 큰 길이만큼 잘랐을 때 마지막 커팅한 위치에서 배열의 끝까지 길이가 남는 것을 간과했다. 이를 수정하기 위해서 S = new int[M+1]로 선언하고 S[M] = L을 추가해 주었다. 그리고 cutCake()의 리턴값이 Q[i]보다 클 경우에 상한값을 올려주고, max값을 갱신해 주었다. 왜냐하면 정상적으로 mid만큼 Q[i]만큼 잘랐을 때 무조건 Q[i]보다 +1 크기 때문이다.

 

<코드 구현>

import java.util.Scanner;
import java.io.IOException;
import java.util.Arrays;
import java.lang.Math;

//[백준] 17179번 - 케이크 자르기 (Java)

public class Main {
    static int N, M, L;
    static int S[], Q[];
    
    public void InputData() throws IOException
    {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        L = sc.nextInt();
        S = new int[M+1];
        for (int i=0; i<M; i++) {
            S[i] = sc.nextInt();
        }
        S[M] = L;
        Q = new int[N];
        for (int i=0; i<N; i++) {
            Q[i] = sc.nextInt();
        }
    }
    public int cutCake(int mid) {
        int prev = 0, count = 0, prev_idx = 0;
        // 마지막 길이인 S[M](L)까지 검색을 한다.
        for (int i=0; i<=M; i++) {
            if (S[i] - prev >= mid) {
                //System.out.println("  S[i]= "+S[i]+", prev= "+prev);
                prev = S[i];
                prev_idx = i;
                count++;
            }
        }
        return count;
    }

	public void Solve(int key) {
        int ans = 0;
        int start = 0;
        int end = L;
        //System.out.println("key= "+key);
        while (start <= end) {
            int mid = (start + end)/2;
            // 중간값(조각의 길이)이 커지면 자른 개수는 줄어든다.
            int count = cutCake(mid);
            //System.out.println("mid= "+mid+", count= "+count);
            // count가 mid 길이만큼 잘랐을 때 k+1이 나온다. 왜냐하면 나머지 길이까지 카운트를 하기 때문이다.
            if (count > key) { // 자른 개수가 key값 보다 많으니까 하한선을 올린다. 
                start = mid + 1;
                ans = Math.max(ans, mid); // 최대값을 계속 저장해 나간다
            } else { // 자른 개수가 key값 보다 적으니까 상한선을 내린다.
                end = mid - 1;
            }
            //System.out.println(" -> start= "+start+", end= "+end);
        }
        System.out.println(ans);
	}
    
	public static void main(String[] args) throws IOException
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        for (int i=0; i<N; i++) {
            m.Solve(Q[i]);
        }
	}
}