[백준] 2343번 기타 레슨 JAVA (자바) 풀이

문제 2531번 (이분탐색)

 :  블루레이에는 총 N개의 강의가 들어가는데,

 :  블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다
    즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

 

 :  M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다 (강의의 길이가 분 단위)

    이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. ( 단, M개의 블루레이는 모두 같은 크기 ) 

 

 

[입력]

 :  첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 블루레이 수 M (1 ≤ M ≤ N)

 :  다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위 (각 강의의 길이는 10,000분을 넘지 않는다)

 

 

[출력]

 :  가능한 블루레이 크기중 최소를 출력

 

 

 [코드]

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

public class Main{
    static int N,M;
    static long sum,cnt;
    static ArrayList<Integer> req = new ArrayList<>();

    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        long max = 0;
        long min = 0;

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            req.add(Integer.parseInt(st.nextToken()));
            max += req.get(i);
            if(min < req.get(i)) min = req.get(i);
        }
        while(min<=max){
            long mid = (min + max)/2;
            sum = 0;
            cnt = 0;

            for(int i=0;i<N;i++){
                if(sum + req.get(i) > mid){
                    cnt++;
                    sum = 0;
                }
                sum += req.get(i);
            }
            if(sum != 0) cnt++;
            if(cnt<=M) max = mid-1;
            else min = mid+1;
        }
        System.out.println(min);
    }
}

 

 [해설]
     

 :  static int N,M; 입력
    static long sum,cnt;  
    static ArrayList<Integer> arr = new ArrayList<>();  순서가 중요하니 arraylist 사용

 

 :   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     StringTokenizer st;
 

 :   N = Integer.parseInt(st.nextToken());  강의수
     M = Integer.parseInt(st.nextToken());  블루레이수
 
 :   long max = 0;  범위가 커서 int가 아닌 long으로 설정
     long min = 0;  범위가 커서 int가 아닌 long으로 설정

 :   st = new StringTokenizer(br.readLine());
     for(int i=0;i<N;i++){ 
            arr.add(Integer.parseInt(st.nextToken())); 강의 개수 만큼 강의 시간 입력받기
            max += arr.get(i);  모든 수의 합
            if(min < arr.get(i)) min = arr.get(i);  강의 시간 비교해서 제일 작은 값을 min으로 설정
     }

 :  while(min<=max){ 
            long mid = (min + max)/2;  min과 max의 평균값을 중앙값으로 설정
            sum = 0;  합 초기화
            cnt = 0;  카운트 초기화

            for(int i=0;i<N;i++){
                if(sum + arr.get(i) > mid){ 합+현재 강의 시간이 중앙값보다 크면 카운트하고 sum은 새로 초기화
                    cnt++;
                    sum = 0;
                }
                sum += arr.get(i);  강의시간끼리 합하기
            }

            if(sum != 0) cnt++;  sum이 0이 아닐 경우 카운트

            if(cnt<=M) max = mid-1;  카운트가 M보다 작을 경우) max를 줄여 다음 mid 값 줄이기
            else min = mid+1;  카운트가 M보다 클 경우) min을 늘려 다음 mid 값 늘리기
        }
        System.out.println(min); 최종결과 출력
    }
}

                            

     

 

이제 풀어보러 갈께요 :)

 

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

2343번: 기타 레슨

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *