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

문제

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

6236번: 용돈 관리

---

문제 요약

앞으로 N일 동안 사용할 금액이 있을 때, 정확히 M번만 통장에서 K원을 인출할 수 있다.

 

이전에 통장에서 뺀 돈으로 하루를 보낼 수 있다면 그대로 사용하고, 모자라면 남은 금액을 통장에 넣고 다시 K원을 인출한다.

 

M번을 맞추기 위해 남은 금액이 사용할 금액보다 많더라도 남은 금액을 통장에 넣고 다시 K원을 인출할 수 있다.

 

최소 금액 K를 출력한다.

---

코드

#include<iostream>
#include<algorithm>
using namespace std;

#define MAX 100002

int n, m, sum, max_;
int arr[MAX];

void binarySearch() {
	int left = max_;
	int right = sum;
	int result = sum;
	while (left <= right) {
		int mid = (left + right) / 2; // 한 번에 인출할 금액
		int money = mid; // 현재 잔액
		int cnt = 1; // 인출 횟수

		for (int i = 0; i < n; i++) {
			// 현재 잔액이 부족한 경우
			if (money < arr[i]) {
				money = mid; // 다시 통장에 넣고 mid원 인출
				cnt++; // 인출 횟수 증가
			}
			money -= arr[i]; // 금액 사용
		}

		if (cnt > m) { // 인출 횟수가 m보다 클 경우
			left = mid + 1; // 인출할 금액을 증가 -> 인출 횟수 감소
		}
		else {
			right = mid - 1; // 인출할 금액을 감소 -> 인출 횟수 증가
			result = mid; // 결과 저장
		}
	}
	cout << result << "\n";
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		sum += arr[i];
		max_ = max(max_, arr[i]);
	}

	binarySearch();

	return 0;
}

---

코드 설명

1. 앞으로 N일 동안 사용할 금액 정보를 입력 받는다.

 

2 - 1. 초기 값 left는 하루에 사용할 금액 중 가장 큰 값, right는 앞으로 사용할 금액의 합으로 설정한다.

+ left를 이렇게 설정한 이유는 mid 값이 하루에 사용할 금액 (arr[i])보다 더 큰 경우만 탐색하기 위해서이다.

+ right를 이렇게 설정한 이유는 1번의 인출로 앞으로 N일을 보낼 경우에 최소 금액이기 때문이다.

+ result도 가장 큰 최소 금액의 경우를 고려하여 right와 같게 설정한다.

 

2 - 2. 이진 탐색을 통해 최소 금액 K를 찾는다.