[백준 2343번 / Java] BOJ 2343 : 기타 레슨(이분 탐색)

 

2343번: 기타 레슨

 

 

 

👇 작성한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public int count(int[] arr, int possible) {
        int cnt = 1, sum = 0;
        // 배열을 돌면서 mid값을 초과하지 않을 정도로 sum에 숫자를 더해준다.
        for(int x : arr) {
            if(sum + x > possible) { // mid 값을 초과한다면, 블루레이 개수 추가
                cnt++;
                sum = x; // 블루레이에 저장할 크기 초기화
            } else sum += x; // mid 값을 초과하지 않는다면 블루레이에 저장
        }
        return cnt;
    }

    public int solution(int M, int[] arr) {
        int answer = 0;
        int lt = Arrays.stream(arr).max().getAsInt(); // arr 배열에서 최댓값 구하기
        int rt = Arrays.stream(arr).sum(); // arr 배열에 있는 모든 값 더하기

        // 이분 탐색 진행
        while(lt <= rt) {
            int mid = (lt + rt) / 2;
            if(count(arr, mid) <= M) { // 블루레이 개수가 M개 이하라면 (정답 가능성 O)
                answer = mid; // 해당 값 저장
                rt = mid - 1; // 오른쪽 포인터를 mid 앞으로 옮기기
            } else lt = mid + 1; // M개를 초과한다면 왼쪽 포인터를 옮기기
        }
        return answer;
    }

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

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());

        Main T = new Main();
        System.out.println(T.solution(M, arr));
    }

}

 

 

느낀 점 및 정리 ✍️

1. 이분 탐색... 쉽지 않다 ... 고려할 내용들이 많아서 푸는 내내 헷갈렸다 ㅜ 설계를 조금 더 꼼꼼하게 하고 들어가야겠다