BOJ(C++) / 백준 16401 : 과자 나눠주기

백준 16401 : 과자 나눠주기

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

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을 출력한다.

 

코드

//백준 16401 과자 나눠주기
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//입력
	int M, N;
	vector<int> L;
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		int l;
		cin >> l;
		L.push_back(l);
	}

	//이분탐색, 이진탐색
	int left = 1, right = *max_element(L.begin(), L.end());
	//left: 가장 작은 수, right: 가장 큰 수
	int snack = 0;
	while (left <= right) {
		int mid = (left + right) / 2; //중앙값
		int count = 0;
		for (int i = 0; i < N; i++) {
			count += L[i] / mid; //mid 과자 길이로 나눠줄수 있는 양
		}
		if (count >= M) { //과자 나눠줄수 있을 때
			left = mid + 1;
			snack = mid;
		}
		else if (count < M) { //과자 나눠줄수 없을 때
			right = mid - 1;
		}
	}
	cout << sum << "\n";

	return 0;
}

 

설명

이분 탐색(이진 탐색) 문제이다.

left는 과자의 길이가 가장 작은 1, right는 과자의 길이가 가장 큰 길이이다.

M명의 조카에게 나눠줄 막대 과자의 최대 길이를 구해야한다. mid 길이로 나눠줄 때 몇명(count)에게 나눠줄수 있는지 구한다.

count가 M보다 작다면 나눠주는 과자 길이가 길어서 다 나눠줄 수 없다는 의미이므로 right를 mid-1로 이동시킨다.

count가 M보다 크거나 같다면 나눠주는 과자 길이가 짧아서 다 나눠줄수있다는 의미이므로 left를 mie+1로 이동시키고, snack은 mid이다. count가 M보다 크거나 같은 과자 길이의 최대를 구해야 한다.

고찰

빠른 탐색을 하기 위해서 이분 탐색을 사용한다. 문제를 보고 접근할 때 이 문제가 이분 탐색을 사용하는 문제인지 바로 알아차리기 어렵다.. 이번에도 역시 이분 탐색 문제인지 모르고 열심히 삽질하다 구글링한 결과 이분탐색 문제라는 것을 알았다. 여러 알고리즘을 생각해보고 그래프인지 DP인지 이분탐색인지 생각해보고 문제를 접근해야 한다.

 

난이도

Silver 3