[오늘의 문제] 승준이의 효율적인 커밋 관리

출처: 항해99 자체 제작

승준이는 N개의 작업을 M일 안에 모두 커밋해야 합니다. 각 작업은 변경된 코드 라인 수를 가지고 있으며, 작업 순서는 변경할 수 없습니다. 하루에 처리할 수 있는 최대 코드 라인 수를 최소화하면서 M일 안에 모든 작업을 커밋하려고 합니다. 하루 최대 처리 가능한 코드 라인 수의 최솟값을 구하는 프로그램을 작성하세요.

입력 형식
첫 번째 줄에 세 개의 정수 N, M이 주어집니다.

N: 작업 기록 개수 (1 ≤ N ≤ 100,000)

M: 작업을 완료해야 하는 일수 (1 ≤ M ≤ N)

둘째 줄에 N개의 정수 L이 주어집니다.

각 정수 L는 변경된 코드 라인의 수를 나타냅니다. (1 ≤ L ≤ 10,000)

출력 형식
M일 동안 모든 작업을 처리하기 위한 하루 최대 처리 가능한 코드 라인 수의 최솟값을 출력합니다.

제약 조건
하루 동안 작업을 나눌 때, 연속된 작업만 같은 날에 포함할 수 있습니다.

모든 작업은 순서대로 커밋되어야 합니다.

모든 작업은 M일 안에 완료되어야 합니다.

힌트
특정 값으로 M일 안에 모든 작업을 처리할 수 있는지 확인하는 것이 가능합니다.

이분 탐색을 통해 가능한 값들 중 최솟값을 찾을 수 있습니다.

예제 입력 1
7 4
2 2 2 2 2 2 2
예제 출력 1
4
예제 입력 2
8 3
10 5 8 2 6 7 2 5
예제 출력 2
16

import java.util.;
import java.io.;

public class Main {
public static boolean isPossible(int m, int[] work, int maxPerDay) {
// 현재 최대 라인수로 m일 안에 모든 작업을 처리할 수 있는지 확인하는 함수
int days = 1;
int currentSum = 0;

    for (int lines : work) {
        // 단일 작업이 하루 최대 작업량보다 큰 경우
        if (lines > maxPerDay) {
            return false;
        }

        // 현재 일에 더 작업을 추가할 수 없는 경우
        if (currentSum + lines > maxPerDay) {
            days++;
            currentSum = lines;
        } else {
            currentSum += lines;
        }
    }

    return days <= m;
}

public static int minLinesPerDay(int n, int m, int[] work) {
    // 이분 탐색을 통해 가능한 최소의 하루 최대 라인 수를 찾는 함수
    int left = Arrays.stream(work).max().getAsInt();  // 하루 최소 필요 라인 수
    int right = Arrays.stream(work).sum();  // 하루 최대 가능 라인 수
    int answer = right;

    while (left <= right) {
        int mid = ____;  // 중간값 계산

        // mid 값으로 m일 안에 처리 가능한지 확인
        if (____) {
            answer = Math.min(answer, mid);  // 현재값이 더 작다면 정답 갱신
            right = ____;  // 더 작은 값 탐색
        } else {
            left = mid + 1;  // 더 큰 값 탐색
        }
    }

    return answer;
}

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[] work = new int[N];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
        work[i] = Integer.parseInt(st.nextToken());
    }

    System.out.println(minLinesPerDay(N, M, work));
}

}

빈칸1: O
정답: (left + right) / 2
해설: 이분 탐색에서 중간값을 구할 때는 시작값(left)과 끝값(right)의 합을 2로 나누어야 합니다. 이때 자바에서는 정수 나눗셈(/)을 사용하여 하루에 처리 가능한 코드 라인 수의 중간값을 구합니다.

빈칸2: O
정답: isPossible(m, work, mid)
해설: 이분 탐색의 각 단계에서 중간값(mid)으로 M일 안에 모든 작업을 처리할 수 있는지 확인해야 합니다. 이를 위해 isPossible 함수에 현재 중간값(mid)을 전달하여 가능 여부를 판단합니다.

빈칸3: O
정답: mid - 1
해설: 현재 중간값으로 M일 안에 처리가 가능한 경우, 더 작은 값도 가능한지 확인하기 위해 오른쪽 경계를 mid - 1로 줄입니다.

이번에는 세문제 다 맞췄다.
문제가 쉬운건지 실력이 늘은건지는 모르겠다.