[알고리즘] C++ 백준 16401 과자 나눠주기

백준 16401

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

16401번: 과자 나눠주기

풀이 전 나의 생각

길이를 가진 N개의 막대 과자가 주어지고 이 막대 과자를 M명의 조카에게 최대한 길게 나눠주려고한다.

단, 막대 과자는 여러 조각으로 나눠질 수 있지만 과자를 하나로 합칠 수는 없다. 

 

예를 들어 3명의 조카와 5, 6, 7, 8, 9의 길이를 가지는 막대 과자 5개가 있다고 가정하자.

3명의 조카에게 최대한 긴 막대 과자를 주기 위하여 3 ~ 5번째 막대 과자를 7의 길이로

나누어 줄 수 있다. (8과 9의 길이 막대 과자는 7의 길이로 뿌셨다.)

 

하지만 길이 8의 막대 과자를 주기 위하여 

7의 길이 막대과자 + 6의 길이의 막대 과자를 뿌셔서 5를 버리고 1을 추가 = 8의 길이 막대과자

이런 형식은 안된다는 것이다.

 

그리고 과자의 길이는 10억과 같거나 작고 과자는 100만 개가 주어질 수 있기 때문에 

10억 길이를 탐색하며 100만 개의 과자를 탐색하려면 이분 탐색이 필요하다.

 

우선 과자의 최대 길이를 구해야 하는 거니깐 탐색해야 할 끝점을 막대 과자의 최대 길이로 지정한다.

이유는 1부터 최대 길이 사이에 우리가 원하는 답이 있기 때문이다.

 

그리고 시작점과 끝점을 이용하여 중간점을 구하고 -> mid = (start + end) / 2

막대 과자를 처음부터 끝까지 탐색하며 중간점을 나눈 값의 누적 합을 구해준다. -> cum_sum += snack[i] / mid;

누적합은 현재 주어진 막대 과자를 이용하여 구한 mid 길이의 막대 과자 개수를 의미한다.

 

mid길이의 막대 과자 개수가 많다면 그만큼 여러명의 조카에게 줄 수 있다는 의미고

현재 존재하는 조카의 수보다 막대 과자 개수가 더 많다면 막대 과자의 길이를 더 길게 해줄 수 있다는 것이다.

그러므로 시작점을 중간점 + 1로 설정하고 최댓값을 갱신 시켜준다.

->

if (cum_sum >= M(누적합이 조카 수 보다 많다면?))

ans = mid; (최댓값 갱신)
start = mid + 1; (시작점 = 중간점 + 1)

 

반대로 mid길이의 막대 과자 개수가 조카의 수보다 적다면 그만큼 막대 과자가 너무 길다는 의미이기 때문에

길이를 더 줄여줘야 한다. 그러므로 끝점을 중간점 - 1로 설정한다. 

현재 기준이 되는 건 조카에게 나눠 줄 수 있는 균등한 길이의 막대 과자 개수 이기 때문에

막대 과자 개수가 적은 수에서 큰 수로 바뀌는 구간은 최대값을 갱신해주지 않는다.

->

else

end = mid - 1; (끝점 = 중간점 - 1)

 

 

이 과정을 반복하여 최종적으로 조카에게 나눠 줄 수 있는 막대 과자의 최대 길이를 구할 수 있다.

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int snack[1000001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int M, N;

	int start = 1;
	int end = 0;
	int ans = 0;

	cin >> M >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> snack[i];
	}

	end = *max_element(snack, snack+N);

	while (start <= end)
	{
		int cum_sum = 0;
		int mid = (start + end) / 2;

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

		if (cum_sum >= M)
		{
			ans = mid;
			start = mid + 1;
		}
		else
		{
			end = mid - 1;
		}
	}
	
	if (ans == 0) cout << "0";
	else cout << ans;
}