백준 2343번 - 기타 레슨 / Java

문제

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

2343번: 기타 레슨

이분 탐색으로 무엇을 찾아야 하는지 감을 못 잡아서 어려웠던 문제.

블루레이의 크기를 이분 탐색으로 찾고, 그때의 개수를 세서 m과 비교해주면 된다.

항상 느끼지만 이분 탐색은 이분 탐색의 대상을 잘 찾기만 해도 반은 풀고 들어가는 유형인 것 같다

 

알고리즘

1. 블루레이의 크기를 이분 탐색한다. 시작 범위는 레슨 크기의 최댓값, 끝범위는 모든 레슨크기의 합이다.

2. 블루레이의 크기를 mid라고 했을 때, mid가 너무 커서 개수가 부족하면 범위를 낮추고, 개수가 많으면 범위를 높인다

3. 블루레이의 개수가 m이 되면 그때의 크기를 출력한다

소스코드

/*
 * BOJ2343
 * 2020.02.07
 * Hyeonseong 
 */
import java.util.*;    
public class BOJ2343 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
    int n; // 레슨의 수
    int m; // 블루레이의 수 
    int les[]; // 강의
    int answer; // 정답 
    public Solution() {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        les = new int[n];
        int start = 0, end = 0;
        answer = 0;
        for(int i=0;i<n;i++) {
            les[i] = scan.nextInt();
        }
        for(int i=0;i<n;i++) {
            if(start < les[i]) {
                start = les[i];
            }
            end+=les[i];
        }
        while(start<=end) {
            int mid = (start+end)/2; // 블루레이의 크기
            if(go(mid)) { 
                answer = mid;
                end = mid-1;
            } else {
                start = mid+1;
            }
        }
        System.out.println(answer);
    }
    public boolean go(int size) {
        int cnt = 0;
        int sum = 0;
        for(int i=0;i<n;i++) {
            if(sum+les[i]>size) { // 레슨크기의합이 사이즈보다 커지면
                cnt++; // 블루레이의 개수를 1개늘리고
                sum = les[i]; // 새로운 그룹을 만든다
            } else {
                sum+=les[i];
            }
        }
        return (cnt>=m) ? false : true;
    }
}