[백준 2343] 기타레슨 - JAVA

문제

---

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

2343번: 기타 레슨

 

 

 

 

 

문제풀이

---

*접근방법

문제의 제한 조건이 강의의 수는 100,000 과 각 강의의 길이는 10,000분이 넘지 않는다고 주어졌다. 여기서 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 만들어야 하는데 최대치를 두고 생각을 했을 때는 너무 터무니 없이 큰 제한이라 블루레이의 크기를 기준으로 이분탐색을 하면 찾을 수 있겠다 라고 생각이 들었다.

그런데 보통 이분탐색은 정렬된 곳에서 찾는게 보통인데 해당 문제에서는 강의의 순서가 뒤바 뀌면 안된다 라고 적혀있다. 따라서 정렬을 하지 않고 블루레이의 길이에 따라 만들어지는 강의의 수를 체크하여 가장 최소의 길이가 되는 블루레이 크기를 구해야한다.

 

 

 

 

 

소스코드

---

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

public class Main {
    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[] lessonList = new int[n];

        int left = 0;
        int right = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            lessonList[i] = Integer.parseInt(st.nextToken());
            right += lessonList[i];
            left = Math.max(left, lessonList[i]);
        }

        while (left <= right) {
            int mid = (left + right) / 2;

            int count = getCount(n, lessonList, mid);

            if(count > m){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        System.out.println(left);
    }

    private static int getCount(int n, int[] lessonList, int mid) {
        int sum = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (sum + lessonList[i] > mid) {
                sum = 0;
                count++;
            }
            sum += lessonList[i];
        }

        if(sum != 0) count++;
        return count;
    }
}