• 아예 같은 문제이다. 똑같은 로직을 복사 붙여넣기 해도 통과한다. 따라서 기타 레슨 코드만 설명하면 될 것이다.

---

문제 이해

숫자 배열을 아래조건을 통해 묶을 것이다.

1. i번째 값과 j번째 값을 같은 묶음에 포함시키고 싶다면, i+1, i+2, ... , j-2, j-1번째 값도 같은 묶음에 포함해야한다. 즉 같은 묶음에는 항상 인접한 index에 존재하는 값이 존재해야 한다.
2. 블루레이의 개수는 한정되어 있다.(이는 M을 통해 입력값으로 주어질 것이다)

이렇게 만든 묶음 들 중 원소의 합의 최댓값을 K라고 하자. 내가 만들 수 있는 묶음은 여러 경우의 수가 존재할텐데, 이 때 K가 가장 작게 되는 경우의 수를 선택하여 이 때의 K를 구하는 문제이다.

---

문제 풀이

부분합의 최소를 구하는 문제이다.
문제는 index의 변화는 절대 불가하다는 것이다.(문제에서 묶음의 조건)
즉, Sorting으로 해결할 수가 없다는 의미이다.

나는 배열의 순서를 건드릴 수 없다. 그렇다면 내가 임의로 지정할 수 있는 것은 무엇인가?
그것은 부분합의 최솟값이다.

예를 들어 내가 부분합의 최댓값을 K으로 정했다면, Array를 차례대로 Search하다가 어느 구간에서 합이 K을 넘어선다면 그 순간 이전 index까지의 값을 한 묶음 처리하고 새로운 묶음을 처리하면 될 것이다.

이 때 발생하는 문제는 무엇인가. 바로 블루레이의 개수가 M개로 한정되어 있다는 것이다.
즉, 묶음의 개수를 따로 계산하여 묶음의 개수와 M을 비교하며 K의 값을 조절하는 것이 필요하다.

묶음의 개수를 count라고 가정할 때, count가 M보다 작더라도 이는 정답이 될 수 있는 후보군이다. 왜냐하면 우리가 지정할 K는 묶음 원소합의 최댓값이다. 즉, count < M일 경우 특정 묶음을 2개로 쪼개도 쪼개는 묶음의 합이 K가 아닌 이상 절대로 K값은 변동되지 않는다. 즉, 2가지 Case로 구분할 수 있을 것이다.

1. count <= M : 정답이 될 수 있는 Case이다.
   우리는 K의 최솟값을 구하고 싶기 때문에 right값을 변경시켜준다.

2. count > M : 정답이 될 수 없는 Case이다.
   K를 크게 해야 묶음에 들어갈 수 있는 원소의 개수가 많아지고, 자연스럽게 count가 감소될 것이다. 즉, K를 크게 해야하므로 left 값을 변경시켜준다.

위 방법을 활용하여 이분탐색을 통해 문제를 풀었다.

참고로 우리는 절대 숫자 Array를 변형시키면 안되기 때문에 Array의 Sorting은 하면 안된다.

---

코드

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

public class Main {
	static int N, M;
	static Integer[] arr;
	
	static void blueray(int left) {
		int right = 1000000000;
        // right 값 도출 이유 : 강의의 길이는 10000 미만이고, 
        // 강의 개수는 100000이하이다.
        // 즉, 총 강의 길이는 최악의 경우에도 10000*100000 미만이므로, 
        // 해당 값을 right으로 지정했다.
		int mid;
		int ans = left;
		
		while(left <= right) {
			long sum = 0;
			int count = 1;
			mid = (left + right)/2;
			
			for(int i =0;i<N;i++) {
				sum+=arr[i];
				if(sum > mid) {
                // 부분합이 내가 지정한 최댓값보다 커졌으므로 새로운 묶음을 만듦
                // 묶음의 개수를 1 증가시킴 & 새 묶음에 지금의 원소를 담아줌
					sum = arr[i];
					count++;
				}
			}

			if(count <= M) {
                // 문제 풀이 1번 상황
				ans = mid;
				right = mid - 1;
			}
			else {
                // 문제 풀이 2번 상황
				left = mid + 1;
			}
		}
		System.out.println(ans);
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		M = sc.nextInt();
		arr = new Integer[N];
		int left = 0;
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextInt();
			if(left < arr[i]) {
				left = arr[i];
			}
		}
		
		blueray(left);
        /*
        left는 배열의 최댓값이다.
        묶음의 합을 구하고 싶은 것이고, 모든 원소는 무조건 한 개의 묶음에는 
        포함되어 있어야 한다.
        
        즉, 배열의 최댓값 또한 한 개의 묶음에 들어가야 하므로, 
        이 값을 left(Search의 최소범위)로 지정하였다
        */
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 6,7,8번째 틀렸습니다
  for문에서 묶음의 개수를 추가시키는 순서는 "묶음의 개수를 추가한다" ⇒ "묶음에 원소를 집어 넣는다" ⇒ "다음 원소를 확인한다"이다.
  즉, sum을 계산하는 for문이 종료될 때 나오는 count가 묶음의 개수이다.
  하지만, 순서를 헷갈려 "묶음에 원소를 집어 넣는다" ⇒ "이 값이 최대값을 넘으면 묶음의 개수를 추가한다" ⇒ "다음 원소를 집어 넣는다"로 순서를 잘못 파악했다.
  이로 인해 묶음의 개수를 제대로 파악하지 못했다.

• 2,3,4,5번째 틀렸습니다 : right값을 잘못 설정하여 생긴 문제이다.