백준 2343 - 기타 레슨

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

문제 풀이

탐색 범위는 (1~10억)이고 연산을 N번 해야 함으로 O(N) or O(NlogN)의 시간복잡도 내에 문제를 해결해야 한다. 탐색 시간을 줄이기 위해서 O(logN)시간 복잡도 내에 탐색을 끝낼 수 있는 이분탐색을 이용해 문제를 해결해야 한다.

이 문제의 함정은 조건 중 순서가 뒤바뀌면 안된다는 조껀이 있기 때문에 레슨이 들어온 순서를 sorting할 경우 틀리게 된다.

• begin을 1로 end를 들어온 값의 합을 준다.
• begin과 end 범위 내에서 이분 탐색을 진행한다.
• 이분탐색을 진행하면서 블루레이를 녹화할 수 있는 영상의 길이가 한 영상의 길이보다 작으면 begin을 움직인다.
• 블루레이에 녹화하는 갯수가 블루레이보다 총 갯수보다 작거나 같을 경우 end를 움직인다.
• 블루레이에 녹화하는 갯수가 블루레이보다 작을 경우 begin을 움직인다.

전체 소스

#include <bits/stdc++.h>
using namespace std;

bool cmp(vector<int> arr, int mid, int M) {
    int sum = 0;
    int count = 1;

    for (int arrIndex = 0; arrIndex < arr.size(); arrIndex++) {
        int value = arr[arrIndex];

        if (value > mid) {
            return true;
        }

        if (sum + value <= mid) {
            sum += value;
        } else {
            count += 1;
            sum = value;
        }
    }

    // 길이가 너무 짧다. begin을 늘려줘야 한다.
    return count > M;
}

int binarySearch(vector<int> arr, int N, int M) {
    int begin = 1;
    int end = 0;
    for (int arrIndex = 0; arrIndex < arr.size(); arrIndex++) {
        end += arr[arrIndex];
    }

    while (begin <= end) {
        int mid = (begin + end) / 2;

        if (cmp(arr, mid, M)) {
            begin = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    return begin;
}

int solution(vector<int> arr, int N, int M) {
    int result = 0;
    result = binarySearch(arr, N, M);

    return result;
}

int main(void) {
    int N, M;
    vector<int> arr;
    cin >> N >> M;

    arr = vector<int>(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    cout << solution(arr, N, M) << '\n';
    return 0;
}