<JUNGOL > 숫자구슬(easy) #4791

문제 : https://www.jungol.co.kr/problem/4791

무엇을 구하는 문제인가?

​M개의 그룹으로 주어진 구슬을 나눌때, 그룹들 각각의 합중 가장 큰 수가 가장 최소가 될수있도록 그룹을 나눌려한다. 이때 의 최솟값을 구하는 문제이다.

​

해결 전략

-각 그룹의 합들중 최대값이 최소가 되야함으로, 각그룹의 합의 최대 마지노선을 k라 정한뒤 k를 이분탐색을 이용하여 찾아주었다.

-low는 arr(그룹에적힌 수)들중 최댓값으로, high = 전체 arr의 합으로 정하였다.

​

알고리즘

1. n, m을 입력받고, n개의 구슬에 적힌 수를 입력받는다.(arr)

2. low = arr중 최댓값, high = 전체 arr의 합으로 한다.

3. low 가 high 보다 작은동안 반복

-mid = (low + high)/2

-mid_res = mid를 넘지않게 구슬을 배열했을 때 나오는 그룹의 수

-mid_res <= m이라면 high = mid - 1

-아니면 low = mid + 1

4. high + 1의 값 출력

​

※주의 할점

함수를 짤때 조건을 주의해가며 짜자.

​

<소스코드>

 

#include <stdio.h>

int n, m;
int arr[310];

int get_res(int x)
{
	int i, j;
	int res = 0, sum = 0;
	for (i = 0; i < n; i++) {
		if (sum + arr[i] <= x) sum += arr[i];
		else {
			sum = arr[i];
			res++;
		}
	}
	if (sum > x) res += 2;
	else if (sum > 0) res++;
	return res;
}

int main()
{
	int i, j;
	int low = -2e9, high = 0;
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		high += arr[i];
		if (low < arr[i]) low = arr[i];
	}
	while (low <= high) {
		int mid = (low + high) / 2;
		int mid_res = get_res(mid);
		if (mid_res <= m) high = mid - 1;
		else low = mid + 1;
	}
	printf("%d", high + 1);
	return 0;
}

​