[백준] 6236 용돈 관리 c++

 

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

6236번: 용돈 관리

인출 횟수를 M 번을 맞춰야하며

모자라면 남은 금액은 통장에 넣고 다시 돈을 인출 할 수 있다.

mid가 k 원이고 돈을 계속 쓰면 감소할 것이므로  k에다가 mid 값을 저장 해주었다.

그 후에 돈이 모자라게 되면 ( num[i]>k ) k=mid 로 해주어 다시 돈을 인출 한것처럼 해주었다.

cnt가 m 보다 크게되면 인출 금액을 더 크게 해주어서 cnt를 줄여주고

cnt가 m보다 작게되면 인출 금액을 더 작게 해주어 더 자주 인출하도록 해주었다.

cnt가 m 하고 같아도 최소금액 K를 구해야하기 때문에 인출금액을 더 작게 해주었다.

#include<iostream>

using namespace std;
int N, M, K, sum; //N일동안 M 번만
int num[100001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		cin >> num[i];
		sum += num[i];
	}

	int left = 1, right = sum, mid, cnt, ans = sum;//왜 left가 0으로 시작되면 안될까?
	bool chk = false;

	while (left <= right)
	{

		mid = (left + right) / 2;
		K = mid;
		cnt = 1;
		for (int i = 0; i < N; i++)
		{
			if (num[i] > mid)
			{
				chk = true;
				break;
			}
			if (K >= num[i])
			{
				K -= num[i];

			}
			else//모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 
			{
				K = mid;
				cnt++;
				K -= num[i];

			}

		}
		//	cout<<right<<"  "<<left<<"  " << mid << endl;
		if (cnt > M || chk)
		{
			left = mid + 1;
			chk = false;
		}
		else if (cnt <= M)
		{
			ans = mid;
			right = mid - 1;
		}

	}

	cout << ans;
}