[BOJ] 6236번_용돈 관리_이분 탐색 (C++)

[문제]

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

N과 M을 입력받고 N일 동안 그날에 사용할 금액을 입력받는다. M번만 통장에서 돈을 뺄 수 있을 때, 한번에 인출하는 최소 금액을 구하는 문제이다. 통장에서 뺀돈을 오늘 사용하고 남으면 내일 사용할 수 있으며, 남은 돈으로 하루를 보내지 못하는 경우에는 남은 금액을 전부 통장에 넣고 다시 돈을 인출한다. 그리고 남은 금액으로 하루를 보낼수 있더라도 M번을 맞추기 위해 남은 금액을 통장에 집어넣고 다시 돈을 인출할 수 있다.

[사용 알고리즘]

이분 탐색

[풀이 핵심]

• N과 M이 같을 경우(M의 최대값)에는 돈을 가장 많이 사용하는 날을 기준으로 매일 그 날과 같은 금액을 인출하면 되므로 'start는 돈을 가장 많이 사용하는 날'이 되고, M이 1일 경우(M의 최소값)에는 한번만 인출 해서 모든날을 사용해야 하므로 'end는 N일 동안 사용해야하는 돈의 총합'이다.
• 이분탐색을 사용해서 출금횟수가 M보다 많아지면 인출하는 금액을 올려주고, 출금횟수가 적거나 같은 경우에는 인출하는 금액을 점점줄여가며 최소인출 금액을 구한다.

[코드]

//boj6236번_용돈 관리_이분 탐색

#include<iostream>
#include<vector>

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;

	vector<int> v;

	int start = 0;
	int end = 0;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);

		start = max(start, num);
		end += num;
	}

	int result = 0;

	while (start <= end) {
		int mid = (start + end) / 2;
		int count = 1;
		int money = mid;

		for (int i = 0; i < N; i++) {
			if (v[i] > mid) {
				start = mid + 1;
			}

			if (money >= v[i]) {
				money -= v[i];
			}
			else {
				money = mid - v[i];
				count++;
			}
		}

		if (count > M) {
			start = mid + 1;
		}
		else {
			end = mid - 1;
			result = mid;
		}
	}

	cout << result;

	return 0;
}