[BOJ/JAVA] 16401번: 과자 나눠주기

16401번: 과자 나눠주기

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

키워드

반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

---

구현

• 나누는것 여러개로 나눌 수 있지만, 하나로 합칠 수 없음에 주의하자.

매개변수 탐색을 이용하여 구현한다.

템플릿

low, high 값은 항상 범위 내로 설정한다.

low = 0

high = 길이가 가장 긴 과자

반복문의 속행 조건은 low≤high 이다.

long mid = (low + high) / 2;

mid 길이로 나눠줄 수 있는지 체크한다.

1. mid 길이로 나눠줄 수 있다면
   • low = mid + 1 값으로 갱신한다.

2. mid 길이로 나눠줄 수 없다면
   • high = mid - 1 값으로 갱신한다.

반복문 종료 시 high를 반환한다.

static long canGive()

mid 길이로 모든 조카에게 나눠줄 수 있는지 체크하는 메소드

개수 계산하기

i번째 과자의 길이를 A_i라고 한다면 A_i/mid 개의 과자가 나온다.

해당 과자의 개수를 전부 더한 값이 M보다 크면 true 아니면 false를 반환한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class java_16401 {

    // M : 조카의 수
    // N : 과자의 수
    static int M, N;

    static List<Integer> snackList;

    public static void main(String[] args) throws IOException {
        // 모든 조카에게 같은 길이의 막대 과자를 나눠주자

        // M명의 조카
        // N개의 과자
        // 조카 1명에게 줄 수 있는 막대 과자의 최대 길이

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        snackList = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            snackList.add(Integer.parseInt(st.nextToken()));
        }

        // 정렬
        Collections.sort(snackList);

        // 계산
        int result = binarySearch();

        System.out.println(result);

        br.close();
    }

    private static int binarySearch() {
        int low = 0;
        int high = snackList.get(snackList.size() - 1);

        while (low <= high) {
            int mid = (low + high) / 2;

            // mid 크기로 모든 조카에게 나눠줄 수 있는지 체크
            if (canGive(mid)) {
                low = mid + 1;
                continue;
            }

            high = mid - 1;
        }

        return high;
    }

    private static boolean canGive(int mid) {
        if (mid == 0) {
            return true;
        }
        // 뒤에서부터 해보자
        // mid 크기로 만들 수 있는지 체크

        int snackCount = 0;
        for (int i = snackList.size() - 1; i >= 0; i--) {
            snackCount += snackList.get(i) / mid;
        }

        return snackCount >= M;
    }
}

---

Uploaded by N2T