[BOJ] 2343 기타 레슨 (Java)

# 출처 : https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

---

# 풀이

 

이분 탐색으로 푸는 문제라고 했는데, 코드를 계속 지저분하게 짜서 결국 사람들 코드를 참고했다.

근데 이번 이분 탐색은 인덱스가 기준으로 나누기 2를 하는 것이 아니라 값을 나누어 비교하는 식으로 결과를 도출했다.

디버깅하면서 하나하나 따라가니 결국은 정답으로 가는걸 봤지만,

어떻게 전체 값과 해당 배열의 최대값으로 해당 문제 풀이로 초래했는지 아직까지 의문이다.

---

# 코드

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

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int N=input[0], M=input[1];
            int[] data = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            // 누적값 미리 계산
            int sumValue = 0, maxValue = 0;
            for(int i=0; i<N; i++){
                sumValue += data[i];
                maxValue = Math.max(maxValue, data[i]);
            }

            // 이분 탐색
            while(maxValue <= sumValue) {
                int count = 0, tempSum = 0;
                int mid = (maxValue + sumValue) / 2;

                for(int i=0; i<N; i++){
                    if(tempSum + data[i] > mid){
                        tempSum = 0;
                        count += 1;
                    }
                    tempSum += data[i];
                }

                if(tempSum !=0) count += 1;
                if(count <= M) {
                    sumValue = mid - 1;
                }else{
                    maxValue = mid + 1;
                }
            }

            System.out.println(maxValue);
        } catch (Exception e) {
            System.out.println(e);
        }
    }
}