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

문제

난이도 : 실버 2
백준 6236번 : 용돈 관리

코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
int arr[100004];

int mx = 0;

bool check(int money)
{
    if (money < mx)  return false;

    int temp = money;
    int cnt = 0;

    for (int i = 0; i < N; i++)
    {
        if (temp - arr[i] < 0)
        {
            temp = money;
            cnt++;
        }

        temp -= arr[i];
    }

    if (temp != money)   cnt++;

    return cnt <= M;
}

int main()
{
    cin >> N >> M;

    int sum = 0;

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

    int low = 0, high = sum;
    int K = INT_MAX;

    while (low <= high)
    {
        int mid = (low + high) / 2;

        if (check(mid))
        {
            high = mid - 1;
            K = mid;
        }
        else
        {
            low = mid + 1;
        }
    }

    cout << K;

    return 0;
}

풀이

이분 탐색 문제
이 문제는 N이 10만까지이고 M이 N까지니까 이중 반복문으로 풀면 10만 * 10만이 나와 시간 초과로 못 푸는 문제이다.
그럼 어떻게 풀어야 할까?? 바로 K의 값을 이분 탐색을 통해 찾아 logN * N = NlogN 의 시간복잡도로 푸는 문제
데이터를 입력받으면서 이분 탐색 범위의 최대 값으로 정할 sum을 구한다.(M이 1일 때 K는 배열의 모든 인덱스의 합임) 그리고 입력 값 중 가장 큰 값을 찾아 mx에 저장해둔다.(이따 설명)
이분 탐색을 위한 템플릿 low를 0, high를 아까 구한 sum으로 지정하고 현우가 한 번 인출하는 K는 최솟값을 구해야 하니까 INT_MAX로 초기화해줌.
mid를 구해 check함수로 넘긴다.
check 함수로 가면 처음엔 money(mid 값)가 아까 구한 mx(배열의 최댓값)보다 작으면 바로 false를 리턴해준다. 만약 돈을 새로 인출해서 K원을 뽑았는데 그 날 쓰는 돈이 K보다 많으면 답이 없다
temp를 money로 초기화 후 배열의 0번째부터 빼주다가 음수가 되는 시점이면 돈을 새로 뽑아야 하니까 temp를 money로 다시 초기화하고 cnt를 증가시킨다(새로 인출한다, 인출 횟수).
반복문이 끝나면 마지막 temp가 money와 같지 않다면 돈을 인출해서 썼다는 것이 되니까 cnt를 증가.
마무리로 cnt가 M보다 작거나 같은지를 리턴한다. cnt가 M보다 작다는 의미는 M을 맞추기 위해 돈이 충분하게 남아도 그냥 새로 인출한다는 뜻임.
그렇게 check가 true면 high를 mid - 1로 줄여 최솟값을 찾아나가면 된다.

결과