[java] 백준 2343번 문제(기타 레슨)

원본 링크 : https://www.acmicpc.net/problem/2343

---

문제설명

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj_2343
{
    static int N, M;
    static int[] lesson;
    static int left, right;

    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());

        lesson = new int[N];

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

        System.out.println(binarySearch(left,right));

    }

    public static long binarySearch(long leftPtr, long rightPtr)
    {
        while(leftPtr <= rightPtr)
        {
            long sum = 0;
            long mid = (leftPtr + rightPtr) / 2;
            int count = 1;

            for (int i = 0; i < N; ++i)
            {
                sum += lesson[i];
                if(sum > mid)
                {
                    sum = lesson[i]; // 새 블루레이 시작
                    ++count; // 블루레이 개수 증가
                }
            }
            if(count <= M) rightPtr = mid - 1; //필요한 블루레이 갯수가 M보다 작거나 같으면
            else leftPtr = mid + 1; //총 필요한 블루레이 개수가 M보다 크다면
        }
        return leftPtr;
    }
}

 

설명

• 이진 탐색의 시작 인덱스는 최대 길이의 레슨이고 종료 인덱스는 모든 레슨 길이의 합이다.
• 총 9개로 구성된 레슨의 시간은 각각 1, 2, 3, 4, 5, 6, 7, 8, 9이므로 이진 탐색의 시작 인덱스는 최대 레슨 시간인 9, 종료 인덱스는 레슨 시간을 모두 합한 45이다.
• 블루레이 개수가 3일 때 9~45 사이에서 블루레이 크기의 최소값을 이진 탐색으로 찾으면 된다.
• 9~45 사이에서 이진 탐색을 아래와 같이 수행한다. 이진 탐색은 leftPtr > rightPtr 일 때까지 수행한다.

1. mid 크기로 모든 레슨을 저장할 수 있으면 rightPtr = mid - 1
2. mid 크기로 모든 레슨을 저장할 수 없으면 lefgPtr = mid + 1

 

 

... 이하 과정 생략