[백준-실버] 기타 레슨 (BOJ 2343)

문제

기타레슨 링크

 

풀이

이분 탐색 문제로 가장 먼저 블루레이의 크기를 정해야 한다. 블루레이의 가장 작은 길이는 배열의 max 값이 되고 가장 큰 길이는 모든 배열의 합이 된다.

max와 sum의 값으로 mid 값을 구한뒤 arr를 반복문을 돌려 inerSum의 값이 mid와 같거나 커지면 count를 증가시키고, 작으면 inserSum에 해당 값을 더해준다.

count <= M 일때 출력값을 mid로 정하고 작았을때를 대비해 max = mid - 1으로 설정해준다. 다른 조건은 start = mid + 1로 설정해준뒤

출력값을 출력해준다.

 

코드

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

public class 기타_레슨 {
    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[] arr = new int[N];

        st = new StringTokenizer(br.readLine());
        int max = 0;
        int sum = 0;
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            max = Math.max(max, num);
            sum += num;
            arr[i] = num;
        }

        // 이분 탐색 시작
        int result = sum;
        while (max <= sum) {
            int mid = (max + sum) / 2;

            int count = 1;
            int currentSum = 0;
            for (int i = 0; i < N; i++) {
                if (currentSum + arr[i] > mid) {
                    count++;
                    currentSum = arr[i];
                } else {
                    currentSum += arr[i];
                }
            }

            if (count <= M) {
                result = mid;
                sum = mid - 1;
            } else {
                max = mid + 1;
            }
        }

        System.out.println(result);
    }
}