백준 2343 - 기타 레슨
백준 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;}