백준 6236 c++ "용돈 관리" -PlusUltraCode-

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

[필자 사고]

이분 탐색 을 이용하는 문제다.

보통 고정관념이 있다. 이분 탐색하면 반드시 배열이 정렬되어 있어야 한다는 착각을 하게 된다.

해당 문제는 그런 이분탐색이 아니라 최소 최대 범위가 주어진 상황에서 mid값을 찾는 거다.

mid값을 찾은 뒤 money[]조건에 맞는 count 갯수를 찾아 mid값을 조정하기 때문에 괜찮다. 

뭐 생각해보면 최소 최대가 정해진 범위 자체가 정렬되어 있는 상황이니 어쩌면 맞는 말 같기도 하다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

canWithDraw(int K)

• 기능: 하루에 사용할 금액 리스트(money)를 주어진 인출 금액 K로 충당할 수 있는지 검사한다.
• 로직:
  1. 현재 사용할 수 있는 돈(distMoney)을 K로 초기화한다.
  2. 인출 횟수(count)를 1로 시작한다.
  3. N일 동안 반복하면서,
     • 만약 distMoney가 오늘 필요한 돈(money[i])보다 적으면 새로 인출한다.
       이때 인출 횟수를 증가시키고, 잔액을 다시 K로 초기화한다.
     • 오늘 필요한 돈을 잔액에서 뺀다.
  4. 마지막까지 돌았을 때, 총 인출 횟수가 M 이하라면 true를 반환하고, 그렇지 않으면 false를 반환한다.

즉, 이 함수는 "인출 금액 K로 모든 날짜를 M번 이하의 인출로 커버할 수 있는지" 여부를 판단한다.

---

main()

• 입력 처리:
  • N과 M을 입력받는다.
  • money 벡터에 N일 동안의 사용 금액을 입력받고, 전체 합(sumMoney)을 계산한다.
  • 또한 하루 중 가장 큰 금액(maxMoney)을 구한다.
• 이분 탐색 준비:
  • 탐색의 하한(left)은 maxMoney.
    이유는 최소한 하루 최대 사용 금액만큼은 인출해야 하루를 버틸 수 있기 때문이다.
  • 탐색의 상한(right)은 sumMoney.
    이유는 모든 날을 한 번에 커버할 수 있는 최대 금액이기 때문이다.
• 이분 탐색 실행:
  • 중간값 mid를 계산한다.
  • canWithDraw(mid)가 참이면, mid 금액으로도 모든 날을 충당 가능하므로 answer를 mid로 갱신하고, 더 작은 금액을 탐색하기 위해 right를 줄인다.
  • 거짓이면, 현재 금액이 부족하므로 더 큰 금액을 탐색하기 위해 left를 늘린다.
• 반복이 끝나면, answer에는 조건을 만족하는 최소 인출 금액이 저장된다.

[소스 코드]

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

int N, M;
vector<int> money;


bool canWithDraw(int K) {
	
	int distMoney = K;
	int count = 1;
	for (int i = 0; i < N; i++) {

		if (distMoney < money[i]) {
			distMoney = K;
			count++;
		}

		distMoney -= money[i];
	}

	return count <= M;
}

int main(void) {
	cin >> N >> M;
	
	money.assign(N, 0);
	int sumMoney = 0;
	for (int i = 0; i < N; i++) {
		cin >> money[i];
		sumMoney += money[i];
	}

	int maxMoney = *max_element(money.begin(), money.end());
	
	int left = maxMoney;
	int right = sumMoney;
	int answer = 0;
	while (left <= right) {
		int mid = (left + right) / 2;
		
		if (canWithDraw(mid)) {
			answer = mid;
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}

	cout << answer;
	
}