2343번 : 기타 레슨 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(31분 41초)

아이디어

일단 큰 포인트는 두 가지이다.

1. 블루레이 길이를 이분탐색으로 찾는다.
2. 해당 길이의 블루레이가 M개 있다면 모든 강의를 "순서대로" 저장이 가능한가?

일단 첫 번째

        // 이분 탐색으로 블루레이 수 찾기
        int left = 1;
        int right = sum;
        int mid=0;
        while (left<=right){
            mid = (left+right)/2;
            //가능하다면 더 작은 수로 해보기
            if(findLen(mid)){
                right = mid -1;
            }
            //안되면 큰 수로
            else{
                left = mid+1;
            }
        }

 

- 만약 findLen에서 true가 return 되었다면 가능한 길이라는 것이다.
그렇다면 최대한 짧은 블루레이의 크기를 가져야함으로 가능할때까지 작은 수로 검증해본다.

 

- 만약 false다?그럼 해당 블루레이 길이로는 부족하다는 의미이므로 수를 키워서 다시 찾는다.

 

그리고 해당 길이의 블루레이가 M개 있다면 모든 강의를 "순서대로" 저장이 가능한가?를 검증하는 코드

    // 해당 길이로 가능한지
    static boolean findLen(int target){
        int cnt =0;
        int temp = 0;
        for(int i=0; i<N; i++){
            if(target<lectures[i]){
               return false;
            }
            if(temp==0|| temp+lectures[i]>target){
                cnt++;
                temp=lectures[i];
            }
            else{
                temp+=lectures[i];
            }
        }
        result = cnt<=M? target:result;
        return cnt<=M;
    }

 

단일 강의의 길이가 검증하고자 하는 블루레이의 길이보다 크다면 무조건 불가능 함으로
return false를 해준다.

 

그것이 아니라면 해당 블루레이 길이로 몇개의 블루레이가 나오는지 cnt로 세어주고
카운트한 값이 문제에서 주어진 M보다 작거나 같다면 가능함으로
true를 return 해준다.

전체코드

import java.io.*;
import java.util.*;
public class Main {
    static int N, M, result;
    static int [] lectures;
    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());
        st = new StringTokenizer(br.readLine());
        lectures = new int[N];
        int sum = 0;
        result = 0;
        for (int i=0; i<N; i++){
            lectures[i] = Integer.parseInt(st.nextToken());
            sum+=lectures[i];
        }

        // 이분 탐색으로 블루레이 수 찾기
        int left = 1;
        int right = sum;
        int mid=0;
        while (left<=right){
            mid = (left+right)/2;
            //가능하다면 더 작은 수로 해보기
            if(findLen(mid)){
                right = mid -1;
            }
            //안되면 큰 수로
            else{
                left = mid+1;
            }
        }
        System.out.print(result);
    }
    // 해당 길이로 가능한지
    static boolean findLen(int target){
        int cnt =0;
        int temp = 0;
        for(int i=0; i<N; i++){
            if(target<lectures[i]){
               return false;
            }
            if(temp==0|| temp+lectures[i]>target){
                cnt++;
                temp=lectures[i];
            }
            else{
                temp+=lectures[i];
            }
        }
        result = cnt<=M? target:result;
        return cnt<=M;
    }
}
/*
블루레이 크기를 이분탐색으로 찾는다
검증할때는 해당 블루레이 크기로 순서대로 강의를 넣어 가능하다면 true return 아니면 false return
*/