[백준] 16401. 과자 나눠주기

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

16401번: 과자 나눠주기

m명에게 과자를 나눠줄 수 있는 과자의 최대 길이를 구해야 한다. 따라서 과자들을 정렬한 후에 이분탐색으로 그 최대 길이를 찾으면 된다. 주의할 점은 다음과 같다.

• 하나의 과자를 여러 조각으로 나눌 수 있다(예제 2 참고). 따라서 주어진 과자 갯수보다 조카 갯수가 더 많아도 가능하다. 따라서 과자들을 탐색하면서 과자 길이로 나눈 값들의 합이 조카 갯수보다 크거나 같으면, 과자를 나눠줄 수 있는 것이다. 

// cnt: 나눠줄 수 있는 과자 갯수
int cnt = 0;
for (int i = 0; i < n; i++) {
	cnt += snack[i] / midLen;
}

• 처음에 과자의 길이로만 나눌 수 있다고 잘못 생각했다. 예를 들어 과자 길이가 각각 2, 4, 7 이면 이분탐색을 할 때 인덱스를 기준으로 이분탐색했다. 즉, 2 또는 4 또는 7만 과자 길이가 될 수 있는 것이다. 그러나 과자 길이는 정수 형태이면 된다. 그리고 최대 값은 가장 긴 과자 길이이다. 즉, 1 ~ 7 사이의 정수가 과자 길이가 될 수 있다.

int minLen = 1; // 과자의 최소 길이
int maxLen = snack[n - 1]; // 과자의 최대 길이(가장 긴 과자 길이)

• result 변수가 있는 이유: 만약 result 변수 없이 midLen 값을 답으로 출력하면, 아예 과자를 나눠주지 못하는 경우 잘못된 값이 출력된다. 예를 들어 조카가 5명이고, 과자 갯수는 3개로 길이가 1, 1, 2라고 가정하자. 
  • midLen은 처음에 1(=1 + 2 / 2)이 된다.
  • 그런데 midLen이 1일 때 나눠줄 수 있는 과자는 4개인데 조카는 5명이므로 나눠주지 못한다. 
  • 따라서 maxLen이 midLen - 1로, 0이 되고 while문을 빠져나오게 된다.
  • 이때의 midLen 값은 1이다. 0을 출력해야 하는데 midLen 값을 출력하면 잘못된 값이 출력된다.
  • 따라서 result 변수를 두어서 나눠줄 수 있는 경우에 있을 때 result 값을 갱신해준다. 나눠줄 수 없는 경우에는 result 값이 한 번도 갱신되지 않으므로 0이다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 시간 복잡도: log1,000,000,000 * n
public class Main {

    static int m; // 조카의 수
    static int n; // 과자의 수
    static int[] snack;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        snack = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            snack[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(snack);

        int minLen = 1; // 과자의 최소 길이
        int maxLen = snack[n - 1]; // 과자의 최대 길이(가장 긴 과자 길이)
        int midLen = 0;
        int result = 0;
        while (minLen <= maxLen) {
            midLen = (minLen + maxLen) / 2;

            // cnt: 나눠줄 수 있는 과자 갯수
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                cnt += snack[i] / midLen;
            }

            // 나눠줄 수 있는 경우
            if (cnt >= m) {
                minLen = midLen + 1;
                result = midLen;
            }
            // 나눠줄 수 없는 경우
            else {
                maxLen = midLen - 1;
            }
        }
        System.out.println(result);
    }
}

 

https://www.acmicpc.net/problem/2805 이 문제랑 유사하다! 둘 다 다시 풀어보자.

2805번: 나무 자르기