[백준 - 2343] 기타 레슨 .java

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

 

<문제 분석>

블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다.
블루레이 크기는 모두 같다.

=> 이진 탐색 알고리즘 선택의 이유

 

-> 첫 강의부터 마지막까지 차례대로 저장하다보면 지정한 블루레이 크기로 모든 강의를 저장할 수 있는지 판별 가능

if) 모두 저장 가능 -> 블루레이 크기 줄이기

    모두 저장 불가능 -> 블루레이 크기 늘리기 

=> 블루레이 크기의 최솟값 알 수 있음

 

<예시 분석>

• start: 강의 중 가장 큰 강의 길이 9 -> 최소 강의 길이
• end: 모든 강의 길이의 합 45 -> 하나의 다 담을 경우의 최대 강의 길이
• mid: (start + end ) / 2
• m: 블루레이 개수
• 결과: m개의 블루레이 개수일때의 블루레이 크기의 최솟값

=> 여기서의 포인트(이거 생각하느라 힘들었다)

• mid 값은 수용할 수 있는 블루레이의 값 -> 어느 강의까지 더하면 mid를 안넘을 수 있는지 구해야한다.
• 이렇게 계산하면 블루레이 개수가 나뉘는데, 개수를 count 변수로 나타낸다.
• count > m (mid값이 너무 작음 -> 더 많은 강의를 블루레이에 담아야함 ) : start = mid +1
• count <= m (mid 값이 충분히 큼 -> 더 적은 강의를 블루레이에 담아야함) : end = mid -1

 

하나의 블루레이에 다 담기면 이후 강의는 새로운 블루레이에서 계산되어야함
-> 합이 0이어야한다.(초기화 필요)
이때, 마지막은 초기화가 안됨 -> 0이 아닐때 개수를 count++;

하나만 생각해야하는 문제가 아니여서 어려웠지만 풀고나니 뿌듯함이 배로 느껴졌다. 조금 재밌을지도;

 

int start = Arrays.stream(lessons).max().getAsInt();
int end = Arrays.stream(lessons).sum();

-> lessons 배열을 스트림으로 변환 

-> 스트림의 최댓값 -> .getAsInt(): 정수로 반환

-> 스트림의 모든 요소를 합한 결과 반환(이미 정수라 정수려 변환하지 않음)

💡

이진 탐색을 통해 최솟값을 찾을 때, 중요한 점은 최솟값을 만족하는 범위를 계속 좁혀 나가는 것이다

즉, count가 m과 같을 때가 아니라 start가 end를 넘어서 start가 더 이상 탐색할 수 없는 값이 될 때의 start 값이 최솟값임을 알아야한다

-> start가 end를 넘어서게 되는 시점은, 가능한 블루레이 크기의 범위가 더 이상 존재하지 않는것을 의미

-> start: 가능한 최소의 블루레이 크기

 

 

 

import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        // 입력 받아 저장
        int n = sc.nextInt();
        int m = sc.nextInt();
        //초기화
        int[] lessons = new int[n];

        //저장
        for(int i = 0; i < n; i++) {
            lessons[i] = sc.nextInt();
        }

        //시작 = 가장 큰 값
        int start = Arrays.stream(lessons).max().getAsInt();
        //끝 = 총합
        int end = Arrays.stream(lessons).sum();

        //이진 탐색
        while(start <= end) {
            int mid = (start + end) / 2;
            int sum = 0;
            int count = 0;

            for(int i = 0; i < n; i++){
                //현재 값과 이전까지의 합이 mid보다 크면 sum 초기화 후 다시 총합 구하기
                if(sum + lessons[i] > mid){
                    count++;
                    sum = 0;
                }
                //mid보다 총합이 작으므로 현재 값도 더하기
                sum += lessons[i];
            }
            //탐색 후 총합이 0으로 초기화 되지 않았으면 아직 더 추가해야하기에 추가
            if(sum != 0) count++;
            //현재 블루레이 개수가 m보다 크면 mid가 작음
            if(count > m ){
                start = mid + 1;
            } else {//현재 블루레이 개수가 m보다 작거나 같으면 mid가 큼
                end = mid - 1;
            }
        }
        //start가 end보다 커질때의 start값이 정답
        System.out.println(start);


    }

}