[BAEKJOON] 6236번 용돈 관리

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

6236번: 용돈 관리

모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다.라는 조건에서 첫 번째 생각은 총 N일동 안 자신이 사용할 금액 중 가장 큰 값 이상이어야 문제조건 자체가 성립된 다는 것이다.

당연한 말인 게 남은 금액을 통장에 집어넣기 때문에 만약 사용할 금액 중 가장 큰 값보다 작다면, K원 인출, K원 집어넣기 무한반복 ,,,,,,,

 

이렇게 첫 번째 조건은 만족한 것 같고, 두 번째로는 정확히 M번을 인출한다는 것인데 이 조건은 어떻게 생각해야 하나 곰곰이 보다가, 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출이라고 했기 때문에 남은 금액이 그날 사용할 금액보다 많을 경우는 통장에 최대한 안 집어넣는 방식을 적용해야겠다고 생각했다.

MAX값(N일동 안 사용할 금액 중 가장 큰 값) 보다 크면서, M번 인출할 때 사용할 금액보다 많을 경우, 통장에 집어넣지 말자.

그렇다면 이건 대체 뭘 이용해야 할까,,,? Greedy인가,,?

한참 생각하다가 내가 지금 알고 있는 조건은 위에서 말한 최솟값과, 문제 자체에서 주어진 최댓값인 점에서 이분탐색으로 들어가도 좋을 것 같다고 생각이 들었다. 

사실 나도 이분탐색이라고 생각이 드는데 너무 많은 시간이 들었고, 조건도 생각보다 까다로웠다.

https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

 

이분탐색이 헷갈리신 분들은 이글에서 매우 잘 설명해주시니 한번 보는 걸 추천해요,,

 

내가 이해하기로는 문제의 답이 두 구간으로 나뉘면 답이 달라지는 경계를 찾는 방식으로 접근하면 된다고 이해했다.

또한 정답이 low가될수도 있고, high이 될수도 있는데 이는 문제 조건에 따라 변경해주어야한다.

소스코드

#include <iostream>
#define MAX 100001
using namespace std;

int n, m, price[MAX];

//최소화된 인출금액 K 구하기
int main() {
	cin >> n >> m;
	int high = 0;
	int low = 0;
	for (int i = 1; i <= n; i++) {
		cin >> price[i];
		//각 이용금액중 최대값을 저장
		high += price[i];
	}
	int cnt, remain, res = 0;
	while (low <= high) {
		//mid값을 최소금액 K라고 정함
		int mid = (high + low) / 2;
		//쓰고 남아 있는 금액 변수
		remain = mid;
		cnt = 1;
		bool possible = true;
		for (int i = 1; i <= n; i++) {
			//인출할 금액보다 K가 작으면 불가능
			if (price[i] > mid) {
				possible = false;
				break;
			}
			else if (price[i] > remain) {
				remain = mid;
				cnt++;
			}
			remain -= price[i];
		}
		// 인출 횟수가 M보다 크다는 말은 금액이 너무 작다는 의미
		if (!possible || cnt > m) low = mid  + 1;
		else {
			res = mid;
			high = mid - 1;
		}
	}
	cout << res;
}

성공!