[Java] 백준 2343 기타 레슨

2343 기타 레슨 문제 링크

문제

#1

• 문제를 읽어봤는데 어떻게 풀어야 겠다는 생각 자체가 안듦..
• 그래서 블로그 풀이 보고 이해하는데 초점을 맞춤
  참고한 블로그

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

class Main {
    static int[] lectures;
    static int N;

    public static int lowerBound(int start, int end, int target) {
        while (start != end){
            int mid = (start + end) / 2;
            if (getCount(mid) > target)
                start = mid + 1;
            else
                end = mid;
        }
        return start;
    }

    private static int getCount(int mid) {
        int count = 1;
        int remain = mid;
        for (int i = 0; i < N; i++) {
            if (remain < lectures[i]) {
                remain = mid;
                count++;
            }
            remain -= lectures[i];
        }
        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        lectures = new int[N];
        int sum = 0;
        int maxBlueray = 0;
        for (int i = 0; i < N; i++) {
            lectures[i] = Integer.parseInt(st.nextToken());
            sum += lectures[i];
            if (maxBlueray < lectures[i])
                maxBlueray = lectures[i];
        }
        System.out.println(lowerBound(maxBlueray, sum, M));
    }
}

• 이분 탐색 알고리즘 문제
  
  
• start, end : 최소 블루레이 크기가 될 수 있는 범위를 표시
• mid : start와 end의 중간값(이분탐색), 최소 블루레이 크기로 의심되는 수
  
  
• getCount(int mid) : mid를 블루레이 크기로 설정한 경우, 블루레이가 몇 개 필요한지 count하는 함수
• mid를 블루레이 크기로 설정한 경우
  • 필요한 블루레이 개수가 M보다 많으면 start를 mid+1로 변경
    • 개수가 M이 되려면 블루레이 크기가 무조건 mid보다 커야되니까
  • 필요한 블루레이 개수가 M보다 적거나 같으면 end를 mid로 변경
    • 개수가 M이 되려면 블루레이 크기가 무조건 mid보다 작거나 같아야되니까
• 그래서 start랑 end가 같아지면 그게 최소 블루레이 크기가 될 것 같아서
• while문 조건을 start != end로 바꿔봄
  
• 정답
• 왜냐면 start랑 end가 답의 범위니까 그 범위가 하나의 수로 좁혀져야 진정한 답..? 오차 없는 답이 될 것 같아서 해봄..
• 암튼 이해는 끝..
• 아직 내 실력으로 혼자 끌어내기 어려운 답이였던 것 같다...