[백준] 과자 나눠주기 (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

---

과거에 풀었던 기억이 나서 쉽게 해결한 문제이다. 배열을 모두 입력 받은 후, 오름차순으로 정렬한다. 그 후 이분탐색으로 나눠줄 수 있는 가장 긴 과자의 길이를 찾는다. 이분탐색을 호출할 때, 배열이 다 정렬되어 있어서 bisearch(L[0],L[N-1])으로 호출했는데 생각해보니 그보다 더 작은 값으로도 과자를 나눌 경우가 있으므로 bisearch(1,L[N-1])로 해야 정답이 된다.

코드에서 매개변수 lo, hi와 mid를 long long 자료형으로 설정했는데 생각해보니 L 배열에 들어오는 값이 int 형 범위 내에 있기 때문에 int 형으로 해도 문제가 없을듯하다. int로 바꿔 제출해도 정답으로 인정받았으니 참고하자.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EA%B3%BC%EC%9E%90%20%EB%82%98%EB%88%A0%EC%A3%BC%EA%B8%B0.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
using namespace std;
int M, N;
int L[1000001];
int res;

void bisearch(long long lo, long long hi)
{
	if (lo > hi) return;
	long long mid = (lo + hi) / 2;
	int cnt = 0;

	for (int i = 0; i < N; i++) 
		cnt += (L[i] / mid);
	if (cnt >= M) {
		if (res < mid) res = mid;
		bisearch(mid+1, hi);
	}
	else{
		bisearch(lo, mid-1);
	}
}


int main()
{
	cin >> M >> N;
	for (int i = 0; i < N; i++) 
		cin >> L[i];
	sort(L, L + N);
	bisearch(1, L[N - 1]);
	cout << res;
}