[백준] 16401번: 과자 나눠주기

문제

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

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

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

입력

첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000) 를 만족한다.

출력

첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.

단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다.

예제 입력 1

3 10
1 2 3 4 5 6 7 8 9 10

예제 출력 1

8

예제 입력 2

4 3
10 10 15

예제 출력 2

7

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ16401 {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());

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

        int[] 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 left=1;
        int right=snack[N-1];

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

            int cnt=0;
            for(int i=0;i<N;i++){
                if(snack[i]>=mid){
                    cnt+=snack[i]/mid;
                }
            }

            // 조카의 수보다 많은 과자를 나누어 줄 수 있다면 과자의 길이를 키울 수 있음
            if(cnt>=M){
                left=mid+1;
            }
            else{
                right=mid-1;
            }
        }

        System.out.println(right);
    }
}

문제를 풀기위해 고려해야할 점은 다음과 같다.

고려할 점

• 조카 모두에게 같은 길이의 과자를 줘야한다.
• 과자는 자를 수 있다.
• 조카에게 동일하게 나누어 줄 수 있는 과자의 최대 길이를 구한다.

과자 길이 이분탐색

// 이분탐색을 위해서는 정렬을 하고 탐색을 시작한다.
Arrays.sort(snack);

int left=1;
int right=snack[N-1];

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

    int cnt=0;
    for(int i=0;i<N;i++){
        if(snack[i]>=mid){
            cnt+=snack[i]/mid;
        }
    }

    // 조카의 수보다 많은 과자를 나누어 줄 수 있다면 과자의 길이를 키울 수 있음
    if(cnt>=M){
        left=mid+1;
    }
    else{
        right=mid-1;
    }
}

과자를 자를 수 있다는 점에 주목해야한다.

예제1을 참고로 설명해보자면 아래와 같은 과자의 길이가 있다고 했을 때

과자의 길이
1 2 3 4 5 6 7 8 9 10

조카에게 나누어주려고 하는 과자의 길이가 3이라고 한다면 4 길이인 과자는 3만큼의 길이로 만들 수 있다.

또한 5 길이의 과자도 잘라서 3 길이로 만들 수 있다.

주목해야할 점은 6 길이 이상부터는 3 길이가 한 번 나오는 것이 아니다. 즉, 6 길이의 과자를 3만큼 만들기 위해 자르면 3 길이의 과자가 두 개 나올 수 있는 것이다.

때문에 cnt값을 세기 위해서는 아래와 같이 과자 길이에서 mid(탐색하고자 하는 과자 길이)로 나눈 몫만큼 더해줘야한다.

int cnt=0;
for(int i=0;i<N;i++){
    if(snack[i]>=mid){
        cnt+=snack[i]/mid;
    }
}

cnt 값을 구했다면 모든 조카에게 나누어줄 수 있는지 확인해야한다.

만약 조카의 수보다 cnt 값이 크다면 과자의 길이를 더 키울 수 있다는 뜻이므로 left=mid+1을 해주어 길이를 키워준다.

반대로 조카의 수보다 작다면 모두에게 나누어줄 수 없으므로 과자의 길이를 줄인다.

if(cnt>=M){
    left=mid+1;
}
else{
    right=mid-1;
}

이 과정을 반복하면 모든 조카에게 나누어 줄 수 있는 과자의 최대길이를 구할 수 있다.

처음에 문제를 풀 때 mid 값보다 과자 길이가 크다면 cnt++ 작업을 해주어 조카에게 나누어 줄 수 있는 과자의 개수를 추가해줬다.

하지만 답이 나오지 않았고 생각해보니 mid의 두 배보다 긴 길이의 과자라면 여러 개를 나눠줄 수 있다는 것이 생각나서 코드를 cnt+=snack[i]/mid로 고쳤다.

또한 left의 초기값을 0으로 설정했더니 mid값이 0이 나올 수 있어 0으로 나누는 런타임 에러가 발생하여 left=1로 초기화해주어 답을 출력했더니 문제를 풀 수 있었다.