[DAY40] 99클럽 코딩테스트 JAVA 백준 기타 레슨 2343번

 

2343번: 기타 레슨

 

🚩 해당 문제는 이분탐색을 활용하여 풀 수 있다.

이분탐색은 시작점 과 끝점을 설정하고 그 중간을 구하여 적절한 값을 찾아가는 방식이다. 

시작점은 0 , 끝점은 문제에서 주어진 최대 값을 넣는것이 보통인데 해당 문제는 이렇게 풀면 안되는 문제여서 범위지정에 대해서 신중하게 생각을 해야한다. 

---

🌘 문제 이해하기 

• 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다.
• 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다.
• 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다.
• 때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다.
• M개의 블루레이는 모두 같은 크기이어야 한다.

---

🌗문제 자세히보기

• 한 블루레이의 크기를 이분탐색으로 구하는 것이다.
• 한 블루레이의 최소 하나의 강의를 꼭 녹화되어야 한다. 즉 블루레이의 최소 크기는 가장 긴 강의 길이 이다. 
• 블루레이의 최대 크기는 모든 강의들 길이 합이다. 

//최소는 right,최대는 left
//강의들
int[] arr = new int[n+1];

int left = 0;        
int right = 0;

st = new StringTokenizer(br.readLine());
for(int i=1;i<=n;i++)
{
    arr[i] = Integer.parseInt(st.nextToken());
    left = Math.max(left, arr[i]); //가장 긴 강의 길이
    right += arr[i]; //모든 강의 길이 합
}

 

이 범위만 잘 지정해주면 나머지는 쉽다.

 

1. 강의 수와 블루레이 수가 동일할 때 

>  블루레이의 크기는 가장 긴 강의 길이가 된다. (각 블루레이의 모든 강의를 담아야 하기위해)

 

이분탐색 으로 임의로 구한 블루레이의 크기대로 강의들을 녹화 할때 

2. 만들어진 총 블루레이의 개수가 만들고자 한 M개의 블루레이 개수보다 클 때

> 블루레이의 크기를 늘려야 한다.  크기를 늘려 블루레이의 개수 줄여야 한다.

 

3. 만들어진 총 블루레이의 개수가 만들고자 한 M개의 블루레이 개수보다 작을 때

> 블루레이의 크기를 줄여야 한다. 크기를 줄여 블루레이의 개수 늘려야 한다. 

 

위의 방식들로 블루레이의 크기의 최소값을 구할때까지 이분탐색을 진행하면 된다. 

---

🌕최종코드

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[] arr = new int[n+1];

        int left = 0;        
        int right = 0;

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

        //강의 수와 블루레이 수가 동일하다면 가장 긴 강의가 블루레이의 크기가 된다.
        if(n == m)
        {
            Arrays.sort(arr);

            System.out.println(arr[n]);
            return;
        }

        int length = right;

        while(left<=right)
        {
            ArrayList<Queue<Integer>> que = new ArrayList<>();

            int mid = (left+right)/2;    
          
            int sum =0;

            que.add(new LinkedList<>()); //블루레이 추가
            int seq = 0;

            for(int i=1;i<=n;i++)
            {
                //강의 추가
                if(sum+arr[i] <=mid)
                {
                    que.get(seq).add(arr[i]);
                    sum += arr[i];
                }   
                else
                {
                    seq++;
                    que.add(new LinkedList<>()); //블루레이 추가
                    que.get(seq).add(arr[i]);
                    sum = arr[i];
                }
            }
            
            //블루레이 개수가 초과되면 블루레이 크기 다시 구하기
            if(que.size()>m)
            {
                left = mid+1;        
            }
            else 
            {   length = Math.min(length, mid);             
                right = mid-1;
            }     
        }

        System.out.println(length);
     }
}