99클럽 코테 스터디 11일차 TIL - 과자 나눠주기

무엇을 새롭게 알았는지 이분 탐색은 단순 정렬된 값만이 아니라, 정답의 후보 범위가 있을 때에도 최댓값/최솟값을 찾는 데 매우 유용하다는 걸 느꼈어. 그리고 count += c / len;처럼 나눠줄 수 있는 조각 수를 누적하는 방식이 깔끔했어. 내일 학습할 것은 무엇인지 내일은 이분 탐색과 비슷한 로직을 활용하는 Parametric Search 개념을 더 익히고, 예를 들어 랜선 자르기 같은 문제도 풀어보려 해.

오늘의 학습 키워드

• 이분 탐색
• 최적화
• 조건 탐색
• 자르기 문제

---

공부한 내용 정리

 

문제는 과자를 잘라서 조카 M명에게 하나씩 나눠주되, 각 조카가 받는 과자의 길이가 최대가 되도록 하는 조건이었다.

단순히 길이마다 나눠지는지 전부 계산하면 비효율적이니까, 가능한 길이의 범위(1 ~ 가장 긴 과자 길이)를 두고 이분 탐색을 적용했다.

핵심은 mid 길이로 자를 때 조카 수 M명 이상에게 줄 수 있는지를 판단하는 함수 isPossible()를 만드는 거였고, 이 함수가 true면 더 긴 길이도 가능한지 확인하고, false면 길이를 줄이면서 탐색했다.

---

소스코드

/*
과자 나눠주기
입력 : M = 조카의 수 범위 백만
      N : 과자의 수 범위 백만
      L : [ ] 과자의 길이
로직 : 가능한 과자 길이 범위 1 ~ max(과자 길이)를
      이분 탐색으로 줄여나가며,
      해당 길이로 M명 이상에게 나눠줄 수 있는지 판단한다.
      조건을 만족하는 가장 긴 길이를 찾는다.
출력 : 1명에게 줄 수 있는 과자의 최대 길이.
      나눠줄 수 없다면 0
*/

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

public class Main {
  public static void main(String[] args) throws IOException {
    // ---- 입력
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] input = br.readLine().split(" ");

    // 조카의 수
    int M = Integer.parseInt(input[0]);
    // 과자의 수
    int N = Integer.parseInt(input[1]);
    // 과자 입력 N개 만큼
    String[] input2 = br.readLine().split(" ");
    int [] cookie = new int[N];

    // 가장 긴 과자의 길이
    int max = 0;
    for (int i = 0; i < N; i++) {
        cookie[i] = Integer.parseInt(input2[i]);
        max = Math.max(max, cookie[i]);
    }
    
    // ---- 로직
    // 이분 탐색, 조카 1명에게 줄 수 있는 최대 과자 길이 탐색
    int left = 1;
    int right = max;
    int result = 0;

    while (left <= right) {
      // 시도할 과자 길이
      int mid = (left + right) / 2;

      if (isPossible(cookie, mid, M)) {
        // 가능하면 저장
        result = mid;
        // 더 긴 길이도 가능한지 확인
        left = mid + 1;
      } else {
        // 불가능하면 과자 길이 줄이기
        right = mid - 1;
      }
    }

    System.out.println(result);
  }

  // 현재 길이로 과자를 잘라서 M명에게 나눠줄 수 있는지
  public static boolean isPossible(int[] cookies, int len, int m) {
    int count = 0;
    // 이 과자로 몇 명에게 나눠줄 수 있는지?
    for (int c : cookies) {
        count += c / len;
    }
    // 총 조각 수가 조카수 보다 많거나 같으면 참
    return count >= m;
  }

}

---

오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음엔 단순하게 최대값에서 내려가면서 조건을 찾으려 했지만, 시간 초과가 날 수 있어서 효율적인 탐색이 필요했다.

• 어떻게 해결했는지

정답이 될 수 있는 길이의 범위를 이분 탐색으로 조여가면서 조건을 만족하는 가장 큰 mid 값을 찾았다.

• 무엇을 새롭게 알았는지

이분 탐색은 단순 정렬된 값만이 아니라, 정답의 후보 범위가 있을 때에도 최댓값/최솟값을 찾는 데 매우 유용하다는 걸 느꼈다.
그리고 count += c / len;처럼 나눠줄 수 있는 조각 수를 누적하는 방식이 깔끔했다.

• 내일 학습할 것은 무엇인지

내일은 이분 탐색 개념을 더 익히고, 랜선 자르기 같은 문제도 풀어봐야겠다.

---