BOJ 6236 - 용돈 관리

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	4746	1537	1093	30.294%

문제

---

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

입력

---

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

---

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

접근

---

문제를 보자마자 금액을 이분 탐색으로 구하면 어떨까하는 생각이 들었다.
시간복잡도가 O(N * log(money)) 값으로, money가 long long의 범위더라도 충분히 계산할 수 있었다.
남은 것은 탐색할 left ~ right 값을 구하는 것 밖에 없었다.
최솟값인 left는, 각 날 이용할 금액중 최댓값이다. (이보다 작으면 하루를 보낼 수 없음!)
최댓값인 right는, K가 1일때 N * 금액의 최댓값인 100,000 * 10,000이다.
남은 것은, 이분 탐색을 구현하는 것 뿐이다.

풀이

---

각 금액 상태(mid)일 때의 cnt 값이 M보다 작거나 같으면 right를 줄인다. cnt값이 작을 때 늘릴 수 있기 때문이다.
그 외의 경우에는 left를 늘린다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int N, M, arr[100000], ans = -1;

int solve(int num)
{
	int cnt = 0, money = 0;
	FUP(i, 0, N - 1)
	{
		if (money < arr[i])
		{
			cnt++;
			money = num - arr[i];
		}
		else money -= arr[i];
	}
	return cnt;
}

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

	CIN2(N, M);
	int left = 0, right = 1000000000;
	FUP(i, 0, N - 1)
	{
		CIN(arr[i]);
		left = max(left, arr[i]);
	}
	while (left <= right)
	{
		int mid = (left + right) / 2;
		int cnt = solve(mid);
		if (cnt > M) left = mid + 1;
		else
		{
			ans = mid;
			right = mid - 1;
		}
	}
	COUT(ans);


	return 0;
}