6236번: 용돈 관리

메모리

시간

1504 KB

20 ms

문제 풀이

일 수 만큼 주어지는 금액대로 매일매일 용돈을 사용해야 하고

그 금액에 맞게 출금 횟수를 맞추어서 출금할 최소 금액을 구하는 문제이다.

출금하고 사용한 금액이 다음 날 사용할 금액보다 크다면 더 출금하지 않고 남은 잔돈에서 사용을 한다.

만약 남은 금액이 다음날 사용할 금액보다 적다면 남은 금액은 재입금한 뒤 출금한다.

이분탐색 문제로 min, max 범위를 정한뒤 중간 값을 구해 주어진 조건에 맞게 좁혀가며 값을 구하는 문제이다.

1번의 출금으로 하루 용돈을 사용할 수 있어야 하니 최소값은 가장 용돈이 큰 날의 값으로 설정하고

max는 최소 1번의 출금이 있어야 하니 모든 용돈의 합으로 설정해주었다.

Code

#include <cstdio>
int arr[100000];
int count_m(int mid, int n)
{
	int count = 0;
	int change = 0;
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > change)
		{
			count++;
			change = mid;
		}
		change -= arr[i];
	}
	return count;
}
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	int mid, min = 0;
	int max = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
		if (min == 0)
			min = arr[i];
		else if (min < arr[i])
			min = arr[i];
		max += arr[i];
	}
	while (min <= max)
	{
		mid = (min + max) / 2;
		if (count_m(mid, n) > m)
			min = mid + 1;
		else
			max = mid - 1;
	}
	printf("%d", min);
	return 0;
}