person3113

늙어서 은퇴하기 전까진 계속 공부하자!!


난이도

22년 12월의 나: 이해가 막히는 부분이 존재… 미래의 나는 제대로 이해하기를…!

=> 문제 푼 당일에 이해 못 한 부분 이해했다!!



문제

블루레이 만들기(Baekjoon: 2343번)

image



풀이

import java.util.Scanner;

public class test {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int[] A = new int[N];
    int start = 0;
    int end = 0;
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
      if (start < A[i])
        start = A[i]; // 레슨 최대값을 시작인덱스로 저장
      end = end + A[i]; // 모든 레슨의 총 합을 종료 인덱스로 저장
    }
    while (start <= end) {
      int middle = (start + end) / 2;
      int sum = 0;
      int count = 0;
      for (int i = 0; i < N; i++) { // middle값으로 모든 레슨을 저장 할 수 있는지 확인
        if (sum + A[i] > middle) {
          count++;
          sum = 0;
        }
        sum = sum + A[i];
      }
      if (sum != 0)
        count++;
      if (count > M)
        start = middle + 1;
      else
        end = middle - 1;
    }
    System.out.println(start);
  }
}



이해한 부분

이해한 부분 1

int count = 0; // 모든 강의를 담는 데 필요한 블루레이 개수
  for (int i = 0; i < N; i++) {
    if (sum + A[i] > middle) { // 블루레이가 담을 수 있는 크기(middle)보다 합이 더 커질 경우
      count++; // 새 블루레이 하나 추가해서, 다음 강의부터 새 블루레이에 담기
      sum = 0; // 새 블루레이에 담을 거니까 지금까지의 sum(이전 블루레이에 담은 강의 시간의 합)은 0으로 초기화
    }
    sum = sum + A[i];
    if (sum != 0) // 아직 블루레이에 담지 못한 강의들(sum)이 있다면
      count++; // 새 블루레이를 하나 추가해서 여기에 나머지 강의 전부를 담는다.
  }
  • middle이 17이라고 가정하면 이해하기 쉽다. 강의 1, 강의 2 ~ 가면서 sum에 계속 더해준다. 강의 1 ~ 강의 5의 합은 15고, 15 + 강의 6 > middle이므로 새 블루레이가 필요하다. 따라서 count++과 sum = 0을 해 준다. (주석 참고) 그 후 강의 6과 강의 7을 담아서 sum은 현재 13이다. 그 후 강의 8을 담으려 하니 13 + 강의 8 > middle이므로 또 count++과 sum = 0을 해 준다. 이 때 count의 값은 count++을 두 번 했으므로 2이다. 마지막으로 강의 8과 강의 9를 sum에다 누적해서 현재 sum은 17이고 종료된다.


이해한 부분 2

if (count > M) // 주어진 블루레이 크기값(middle)일 때  모든 레슨을 저장하기에 부족한 경우
  start = middle + 1; // start를 오른쪽으로 옮겨서 다음의 middle값이 더 커질 수 있도록
else // 주어진 블루레이 크기값(middle)일 때  모든 레슨을 저장할 수 있는 경우
  end = middle - 1; // end를 왼쪽으로 옮겨서 다음의 middle값이 더 작아질 수 있도록
  • 앞에서 주어진 middle값(각 블루레이의 크기)에 따라 필요한 블루레이 개수를 구했다. 만약 강의 전체를 담는데 블루레이 4개가 필요하다면(count가 4라면) M보다 크므로(M이 3으로 입력받았을 때) 각 블루레이의 크기를 늘려야지 3개로 전 강의를 담을 수 있을 것이다. 따라서 start를 middle + 1로 해서 다음에 M을 (start+end) / 2로 계산할 때 M의 값을 증가할 수 있다.



이해 못한 부분

  • 앞의 while문을 마친 후 모든 강의를 담을 수 있는 블루레이 크기 중 최솟값을 출력한다. 이 때 start를 출력한다(System.out.println(start)). 왜 start가 최솟값이라고 할 수 있는가?
    • start는 9이고, middle(블루레이 크기)이 17일 때도 크기가 충분하다고 치자. 그럼 계속 end와 middle을 줄여서 이보다 더 크기가 작으면서 모든 강의를 저장하기에 충분한 것을 찾는 시도를 해본다. 그런데 그 후 middle 값의 크기가 충분하지 않아서 계속 start와 middle값을 늘려가며(start 값은 기존의 9에서 13,15,16으로 / middle 값도 14,15,16으로 늘려가며) 크기가 충분한 middle값은 없는지 찾아본다.
    • 그렇게 start와 middle값을 늘리는 어느 순간에 start 혹은 middle이 그 전에 가능했던 바로 전의 middle(=17)이 되버린다(start>end / 즉 start> 전의 middle값 - 1 / 즉 start와 전에 저장 가능했던 middle값이 같아지고, 그 이상으로는 start값이 커져서 다음 middle값도 17보다 커지는 경우 / 그럼 이 때는 더이상 탐색할 필요 없지). 그럼 결국 17보다 작으면서 저장하기에 충분한 크기는 없었다는 뜻이 된다. 그리고 이 때 start 값은 전에 저장 가능했던 middle값 17과 같아딘다. 그럼 이걸 출력하면 모든 강의를 저장 가능한 크기 중 최솟값을 출력하게 되는 것이 아닌가!

참고