[백준/알고리즘] 6236번 용돈관리 (실버 3)

클릭하면 백준 페이지로 이동합니다.

 

---

 

BOJ 6236번

 

현우는 통장에서 정확히 M번 인출하여 N일동안 돈을 사용하려고 한다.
각각의 날 동안 사용하는 금액은 N줄 동안 입력을 받는다.
현우는 하루에 최대 10000원까지 이용을 하고, 최대 100000일동안 계획을 짠다.
이때 한번에 인출할 수 있는 금액을 K라고 했을 때, 현재 가지고 있는 돈이 부족한 경우, 돈을 모두 집어넣고,
K만큼 다시 인출한다. (정확히 M번 맞추기 위해 부족하지 않아도 인출 할 수 있다.)

 

풀이 알고리즘 : 분할정복, 이분탐색

 

현우가 사용할 돈의 범위를 이용해 이분탐색으로 해결하였다.

초기 초기값은, 

 

돈의 최솟값 : 1 원

돈의 최댓값 : 10000 * 100000 원

 

으로 초기화하였고, 이분탐색 과정마다 현재 최대값(mid)으로 계산하였을 때, 몇 번 인출하는지를 cnt로 계산하였다.

 

cnt가 m보다 작으면, mid 값이 너무 큰 경우이고,

cnt가 m과 같으면, 답이 될 수 있지만, 더 작은 최솟값이 존재할 수 있으므로 mid값을 줄여준다.

마찬가지로 cnt가 m 보다 크면, mid 값이 너무 작은 경우이다.

 

주의해야 할 점은, 문제에서 정확히 M번 맞추기 위해, 돈이 부족하지 않아도 인출 할 수 있다는 것을 처리를 따로 해야 한다.

 

소스코드 보기

 

/*
    BOJ 1956 (https://www.acmicpc.net/problem/6236)
*/

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int main(void) {
	// For fast IO
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m, k = -1;	// n일동안 m번만 출금, 출력할 값(최소 금액)
	ll le, ri;			// 이분탐색을 위한 변수
	vector<ll> money;	// n일 각각에서 사용해야 할 금액

	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		ll day;
		cin >> day;
		money.push_back(day);
	}

	le = 1, ri = 1000000000;	// 최대 만원이 십만번 입력 가능

	while(le <= ri) {
		bool isover = false;	// 최대 금액으로도 하루를 사용하지 못하는경우
		ll mid = (le + ri) / 2;	// 이번 탐색에서의 금액
		ll cnt = 0, cur = 0;	// 몇 회 인출했는지, 현재 잔액

		for(int i = 0; i < n; i++) {
			if(mid < money[i]) {	// 최대금액 < 사용해야하는금액
				isover = true;
				break;
			}

			if(cur < money[i] || m - cnt == n - i) {
				// 1. 잔액이 부족한 경우 잔액 충전
				// 2. 정확히 M번을 맞추기 위해 다시 인출
				cnt++;
				cur = mid;
			} 

			cur = cur - money[i];
		}

		if(isover || m < cnt) {
			// 최대 잔고가 너무 낮은 경우, 더 많이 인출 한 경우
			// : 금액을 높여야 함
			le = mid + 1;
		} else if(m == cnt) {
			// 딱 맞게 인출 한 경우 : 저장 후 최소 금액이 존재하는지 확인
			k = mid;
			ri = mid - 1;
		} else {
			// 적게 인출 한 경우 : 금액을 낮춰야 함
			ri = mid - 1;
		}
	}

	cout << k << "\n";

	return 0;
}