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

https://www.acmicpc.net/problem/16401

- 오늘의 학습 키워드

과자 나눠주기

- 풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt(); // 조카 수
        int N = sc.nextInt(); // 과자 수
        int[] snacks = new int[N];

        for (int i = 0; i < N; i++) {
            snacks[i] = sc.nextInt();
        }

        int result = solution(M, snacks);
        System.out.println(result);
    }

    public static int solution(int M, int[] snacks) {
        int maxLen = 0;
        for (int len : snacks) {
            maxLen = Math.max(maxLen, len); // 가장 긴 과자 길이
        }

        int left = 1;
        int right = maxLen;
        int result = 0;

        while (left <= right) {
            int mid = (left + right) / 2;

            long count = 0;
            for (int len : snacks) {
                count += len / mid; // mid 길이로 나눌 수 있는 조각 수
            }

            if (count >= M) {
                result = mid;     // 가능한 경우, 더 큰 길이도 시도
                left = mid + 1;
            } else {
                right = mid - 1;  // 불가능하면 더 작은 길이 탐색
            }
        }

        return result;
    }
}

 

- 오늘의 회고

만약 이 문제를 완탐으로 풀면 10억번을 확인해야 해서 시간 초과가 난다.

때문에 이분 탐색으로 풀어야 한다.