백준 6236번: 용돈 관리 (C++)

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

6236번: 용돈 관리

 

풀이

이해가 조금 어려웠던 문제.

 

돈이 남아도 다시 인출할 수 있기 때문에 큰 금액은 M 번에 맞춰 뽑을 수 있다.

그래서 돈이 모자랄 때 뽑는 경우를 M 과 비교하며 이분 탐색을 진행했다.

 

is_possible 함수에 구현했는데 코드를 보면 이렇다.

bool is_possible(int mid) {
	int cnt = 1;
	int tmp = mid;

	for (int i = 0; i < v.size(); i++) {
		if (mid < v[i]) return false;
		if (tmp - v[i] < 0) {
			cnt++;
			tmp = mid;
		}
		tmp -= v[i];
	}

	if (cnt <= M) return true;
	return false;
}

현재 금액 (tmp)에서 하루에 이용할 금액 (v[i])을 빼면서 반복문을 돌려주었는데

만약 그 값이 0보다 작다면 다시 인출해야하니 cnt 에 1을 더해주고 현재 금액을 초기화 시켰다.

 

그리고 제출했다가 틀렸는데 예외 처리로 현재 금액 (tmp)은 하루에 이용할 금액 (v[i])보다는 커야하기 때문에 

현재 금액 (tmp)이 작은 경우가 있다면 false 를 반환시켰다.

 

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> v;

bool is_possible(int mid) {
	int cnt = 1;
	int tmp = mid;

	for (int i = 0; i < v.size(); i++) {
		if (mid < v[i]) return false;
		if (tmp - v[i] < 0) {
			cnt++;
			tmp = mid;
		}
		tmp -= v[i];
	}

	if (cnt <= M) return true;
	return false;
}

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

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

	int left = 1, right = 1e9 + 2, ret = -1;

	while (left <= right) {
		int mid = (left + right) / 2;
		if (is_possible(mid)) {
			ret = mid;
			right = mid - 1;
		}
		else left = mid + 1;
	}
	cout << ret;
}