[java백준] 실버 1/ 2343번 기타레슨

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

2343번: 기타 레슨

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main {
    public static int n;
    public static int m;
 
    public static int arr[];
 
 
 
    public static void main(String args[]) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st=new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        arr=new int[n];
        st=new StringTokenizer(br.readLine());
        int end=0; // 전체 크기의 합 (전체 다 선택)
        int start=0;//각각의 블루레이 중 가장 큰 값 여기선 9가 될 것 (딱 하나만 선택하는 경우)
        //딱 하나만 선택하는 모든 경우의 수를 고려하려면 원소 중 가장 큰 값이 start로 와야함.
        for(int i=0;i<n;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            end += arr[i];
            if (start < arr[i]) {
                start = arr[i];
            }
 
        }
 
 
        while(start<=end){
 
            // 이진탐색의 기준은 블루레이의 크기
            int mid=(start+end)/2;
 
            int sum=0;
            int cnt=0;
            for(int i=0;i<n;i++){
 
                if(sum+arr[i]>mid){
                    sum=0;
                    cnt++;
                }
                sum+=arr[i];
 
            }
            if(sum!=0){
                cnt++;
                //마지막에 잔류하는게 있으면 cnt에 하나더 더해줘야함
            }
 
 
            if(cnt>m){
                start=mid+1;
            }else{
                end=mid-1;
            }
 
 
 
 
 
        }
 
        System.out.println(start);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    }
 
}
 

 

생각해보면 end에 들어갈 블루레이는 가장 큰 크기가 될 것이니 원소의 모든 값을 더한 것이 될 것이다.

그렇다면 start에는 어떤 것이 들어가느냐가 관건이 된다. 

가장 많이 나눠질 수 있는게 즉, m이 n일때인데,  이런 경우는 블루레이 하나에 각각 한개의 영상이 들어가는 경우이다.  한개의 영상이 들어가려면 원소 중 가장 큰 값이 기준이되어야 할 것이다. 그러니 start에는 원소들 중 가장 큰 값이 들어간다.

 

start와 end를 찾았으면 문제를 다 푼것이나 마찬가지이다. 

 

그리고 문제 풀며 놓친게 하나 있는데

 if(sum+arr[i]>mid)

조건문에서 sum+arr[i]를 판단해줘야했다. 그리고 나서 sum에다 arr[i]를 넣어줘야 했다. ! (뭐가 다른지 의아할 수 있는데 그래야 sum값에 손상이 가지 않는다..!)