[ BOJ ][JAVA][17179] 케이크 자르기

www.acmicpc.net/problem/17179

17179번: 케이크 자르기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	490	176	112	32.749%

문제

생일을 맞이한 주성이가 생일 파티를 준비하려고 한다. 주성이는 일반 케이크 대신 평소 좋아하던 롤 케이크를 준비했다. 롤 케이크에는 장식이 존재해서 특정 위치에서만 자를 수 있다. 주성이는 롤 케이크 조각을 파티에 올 친구의 수 만큼 준비하고 싶어서, 가장 작은 조각의 크기를 미리 알아보기로 했다. 하지만 짓궂은 주성이의 친구들은 생일파티에 몇 명이 참석하는지 직접적으로 알려주지를 않는다. 그래서 몇 개의 수를 목록에 적어, 각 수만큼 조각을 만들었을 때 가장 작은 조각의 길이의 최댓값을 구하려고 한다.

예를 들어 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 p17179 {
    static int n, m, cakeLen;
    static int[] arr;
    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());
        cakeLen = Integer.parseInt(st.nextToken());
        arr = new int[m + 1];
        for (int i = 0; i < m; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        arr[m] = cakeLen;

        while (n-- > 0) {
            int k = Integer.parseInt(br.readLine());
            int answer = 0;
            // 최소 1번 자르는 것, 최대 m번 자르는것.
            // int lo = 1, hi = m;

            // 최소 길이 10, 최대 길이 arr[m-1];
            int lo = 0, hi = arr[m];
            while (lo <= hi) {
                int mid = (lo + hi) / 2;

                // 1. k번 잘라서 길이 35(가운데)가 되도록 케이크를 자를 수 있는가? 없는가? 의 결정 문제
                if (cut(mid, k)) {
                    lo = mid + 1;
                    answer = Math.max(answer, mid);
                } else {
                    hi = mid - 1;
                }
            }
            System.out.println(answer);
        }
    }
    // count의 횟수로 케이크를 잘라서 조각 길이 mid가 나올 수 있는가?
    static boolean cut(int mid, int count) {
        int prev = 0;
        int cnt = count;
        for (int i = 0; i <= m; i++) {
            if (arr[i] - prev >= mid) {
                cnt--;
                prev = arr[i];
            }
        }
        return cnt < 0 ? true : false;
    }
}

ver2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class p17179 {
    static int n, m, cakeLen;
    static int[] arr;
    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());
        cakeLen = Integer.parseInt(st.nextToken());
        arr = new int[m + 1];
        for (int i = 0; i < m; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        arr[m] = cakeLen;
        while (n-- > 0) {
            int k = Integer.parseInt(br.readLine());
            int answer = 0;
            // 최소 1번 자르는 것, 최대 m번 자르는것.
            // int lo = 1, hi = m;
            // 최소 길이 10, 최대 길이 arr[m-1];
            int lo = 0, hi = arr[m];
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                // 1. k번 잘라서 길이 35(가운데)가 되도록 케이크를 자를 수 있는가? 없는가? 의 결정 문제
                int cur = 0, cut = 0;
                for (int i = 0; i <= m; i++) {
                    if (arr[i] - cur >= mid) {
                        cur = arr[i];
                        cut++;
                    }
                }
                // 2. 조건에 따라 최적화하는 최적화 문제
                if (cut > k) {
                    lo = mid + 1;
                    answer = Math.max(answer, mid);
                } else {
                    hi = mid - 1;
                }
            }
            System.out.println(answer);
        }
    }

}