[백준 6236번] 용돈 관리 (C++)

문제링크 : https://www.acmicpc.net/problem/6236

6236번: 용돈 관리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, arr[100001];
int sum;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> arr[i];

    int l=0, r = 1000000000, result = 0;
    while(l<=r)
    {
        int mid = (l+r)/2; //인출 금액
        bool flag = 1;
        int tmp = mid; //남은 돈 (초기 인출값)
        int cnt = 1; //인출 횟수

        for(int i=0; i<N; i++)
        {
            if(arr[i] > mid) //사용할 금액이 인출한 금액보다 큼
            {
                flag = 0;
                l = mid + 1; //인출할 금액이 더 높아야 함
                break; //더 이상 탐색의미가 없음
            }

            if(arr[i] > tmp) //사용할 금액이 남은 돈보다 큼
            {
                tmp = mid; //남은 돈 넣고 다시 K원 인출
                cnt++;
            }
            
            tmp -= arr[i]; //하루 보냄
        }

        if(!flag) continue; //현재 인출금액은 불가능하므로 스킵
        if(cnt > M) l = mid + 1; //인출 금액을 증가시킴
        else 
        {
            result = mid;
            r = mid - 1; //인출 금액을 감소시킴
        }
    }

    cout << result;

    return 0;
}

문제를 잘못 이해하여 다소 애를 먹었던 이분탐색 문제이다.

l = 0, r = 최대금액 10억 (100000 * 10000), mid = 인출금액으로 잡고 탐색을 시작한다.

 

그리고 이어서 현재 인출한 금액이 사용할 금액보다 큰 지를 체크할 bool 변수 flag, 

현재 남은 돈을 체크할 변수 tmp,

인출 횟수를 체크할 cnt를 선언하고 시작한다.

tmp의 경우 초기 인출금액을 이용해 mid 값을 설정해주고,

cnt의 경우 초기 인출금액을 사용했으므로 1로 설정해준다.

 

이제 for문으로 현재 인출 금액이 모든 요일에 사용할 금액에 대해 가능한지 체크를 해준다.

만약 사용할 금액이 인출할 금액보다 크다면 인출할 금액이 더 커져야 한다.

따라서 l = mid + 1을 해주고 더 이상 탐색의미가 없으므로 flag = 0을 하고 바로 for문을 종료시켜준다.

 

만약 사용할 금액이 남은 돈 보다 큰 경우에는 남은 돈을 넣고 다시 새롭게 mid 만큼 인출을 해준다.

따라서 tmp에 바로 mid 값을 설정해주고 인출을 했으므로 cnt의 횟수를 증가시킨다.

 

이제 사용할 금액보다 돈이 확실하게 많이 있으므로 무사히 하루 보내기가 가능하다.

따라서 현재 남은 돈에 사용할 금액을 빼주고 하루가 지나게 된다. (다음 인덱스 탐색)

 

이렇게 for문이 끝나고 이제 인출 횟수를 체크해야 한다.

우선 앞서 flag가 0이 되었을 때 이미 인출할 금액을 더 높게 설정해줬으므로 이후 과정에 대해 스킵한다.

 

다음으로 인출 횟수가 지정한 M보다 높은 경우에는 인출 금액이 적어서 벌어진 일이므로, 인출할 금액을 더 증가시켜줘야 한다.

만약 인출 횟수가 지정한 M보다 작거나 같은 경우에는 인출 금액이 커서 벌어진 일이므로, 인출할 금액을 더 감소시켜줘야 한다.

이때 같은 경우가 포함되어 우리가 원하는 경우와 겹치므로 이때의 mid 값을 따로 저장해준다.

이분탐색을 계속 이어가며 더 적합한 값을 찾아가게 되고, 이렇게 찾은 mid 값을 출력해주면 된다.