[C++] 백준 6236번 - 용돈 관리

 

문제 6236번

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

 

 

최소 금액을 1로 잡고 최대 금액을 사용할 금액의 합으로 잡는다. 그리고 그 사이의 mid 값을 구해서 mid를 temp변수에 넣고 temp가 사용할 금액(money[i])보다 어떠한지 비교해준다.

사용할 금액보다 temp가 더 크거나 같다면 그대로 temp에서 사용할 금액을 빼준다. 만약 아니라면 사용할 수 있는 금액은 다 사용했다는 것이기 때문에 temp에 인출할 수 있는 돈 mid를 넣어주고 통장에서 빼야되기 때문에 1증가시켜준다.

이제 다시 그 다음 사용할 금액(money[i])과 temp를 비교해서 사용할 금액이 더 크다면 false(인출 금액을 더 키워줘야해서 left를 mid+1로 이동)를 반환해주고, 아니라면 temp에 사용할 금액을 빼준다. 그렇게 반복문을 다 돌았다면 통장에서 빼준 수(count)가 통장에서 빼는 수(M)보다 작거나 같은지 확인하여 true(인출 금액을 줄여주기 위해 right를 mid-1로 이동하고 result에 mid값을 넣어줌)나 false를 반환한다. 

그렇게 반복문을 마치고 result값을 출력해주면 인출해야할 최소 금액이다.

 

#include <iostream>
using namespace std;

int N, M;
int* money;
bool check(int mid) {
	int temp = mid;
	int count = 1;
	for (int i = 0; i < N; i++) {
		if (money[i] <= temp) {
			temp -= money[i];
		}
		else {
			temp = mid;
			count++;
			if (money[i] > temp) {
				return false;
			}
			else {
				temp -= money[i];
			}
		}
	}
	return count <= M;
}

int main() {
	cin >> N >> M;
	money = new int[N];
	int sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> money[i];
		sum += money[i];
	}
	
	int result = 0;
	int left = 1, right = sum;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (check(mid)) {
			right = mid - 1;
			result = mid;
		}
		else {
			left = mid + 1;
		}
	}
	cout << result;

	return 0;
}