백준 2343번) 기타 레슨 (JAVA)

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

2343번: 기타 레슨

 

#문제

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

 

#알고리즘

이분탐색

매개 변수 탐색

 

#난이도

Silver 1

 

#풀이방법

계속해서 이분탐색을 정복하려고 풀이를 리뷰하고 있다. 이거 보는 사람이 있을려나??....ㅋㅋㅋㅋㅋ

이분탐색을 이해하고 그것을 문제에 적용하려고 했는데 탐색을 어떻게 해야 하는지 참 난감했다....

탐색범위를 찾고 찾다가 도저히 안돼서 풀이를 보니 문제에서 제시하는 블루레이의 최소크기와 블루레이의 최대 크기를 

설정하고 그 조건에 맞는 블루레이 개수 안에서 블루레이의 최소 크기를 찾으면 되는 것이다.

 

블루레이의 최솟값은 강의 중 가장 큰 것으로 설정하고

블루레이의 최대값은 모든 강의를 더해준 것으로 설정한다.

 

int start = 0;//블루레이의 최소값
        int end = 0;//블루레이의 최대값
        
        for(int i=0; i<lec.length; i++) {
            
            lec[i] = sc.nextInt();//강의 입력
            end += lec[i];
            
            if(start < lec[i])
                start = lec[i];
            
        
        }

 

 

 

 

while(start <= end) {
            
            int mid = (start + end)/2;
            int sum = 0;
            int blue = 1;
            
            for(int i=0; i<lec.length; i++) {
                
                if(sum + lec[i] > mid) {
                    sum = lec[i];
                    blue++;
                }
                else {
                    sum += lec[i];
                }
                
            }
            
            if(blue <= M) {
                end = mid-1;
                an = mid;
            }
            else {
                start = mid + 1;
            }
            
        }

 

 

임시의 블루레이의 크기는 mid = (start + end)/2 로 정하고,

그 안에서 강의들을 더하다가 임시의 블루레이 값을 넘기는 경우 초기화 시켜주고 아직 안넘을 경우 계속 더해준다.

 

블루레이의 개수가 조건보다 작거나 같을 경우(자격이 되는 경우)

end = mid-1;

an = mid;

대입하고, 아닐 경우

start = mid +1;

로 설정한다.

 

#주의 해야 할 점

나같은 경우는 풀이를 했음에도 자꾸 8퍼에서 틀렸습니다가 나와서 왜 그러지?라고 고민하다가 무심코 이분탐색이라는 생각 때문에 Arrays.sort로 배열을 무지성 정렬해버렸다.

 

문제 조건에는 강의 순서가 다르면 안된다는 조건을 무시한 것이다. 

이분탐색 문제라도 무조건 정렬해야 한다는 생각을 버리고, 문제를 꼼꼼히 읽고, 다양한 문제를 접하여 탐색 조건을 찾는 

연습을 해야겠다... 분발하자!

 

#전체 코드

 

import java.util.*;
//3t, 이분탐색, 이분탐색이라는 고정관념 때문에 무지성을 Arrays.sort를 이용하여 배열을 정렬하였다..
// 
 
public class Main {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int[] lec = new int[N];
        
        int M = sc.nextInt();
    
        int start = 0;//블루레이의 최소값
        int end = 0;//블루레이의 최대값
        
        for(int i=0; i<lec.length; i++) {
            
            lec[i] = sc.nextInt();//강의 입력
            end += lec[i];
            
            if(start < lec[i])
                start = lec[i];
            
        
        }
        
        int an = end;
        
        while(start <= end) {
            
            int mid = (start + end)/2;
            int sum = 0;
            int blue = 1;
            
            for(int i=0; i<lec.length; i++) {
                
                if(sum + lec[i] > mid) {
                    sum = lec[i];
                    blue++;
                }
                else {
                    sum += lec[i];
                }
                
            }
            
            if(blue <= M) {
                end = mid-1;
                an = mid;
            }
            else {
                start = mid + 1;
            }
            
        }
        
        System.out.println(an);
            
    }
    
 
}