-
[BOJ 2343][C++] 기타 레슨Algorithm/BOJ 2022. 2. 16. 09:38
문제 유형 : Binary Search Algorithm
저번에 푼 백준 '공유기 설치'와 비슷한 문제이다. (https://blog.naver.com/rlaghdrl333/222578620043) 공유기를 블루레이 갯수라고 생각하고 설치 거리를 블루레이 강의의 길이라고 생각하면 매우 비슷한 문제다. 따라서 '공유기 설치'를 풀어보고 이 문제를 풀거나 이 문제를 풀고 '공유기 설치'를 풀면 간단하다. (WA를 받았던건 비밀) 다만 주의해야 할 점이 있다면 i번 강의와 j번 강의를 같은 블루레이에 녹화해야 하므로 정렬을 쓰면 안된다!
* C++ Code
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M; cin >> N >> M;//강의의 수, 블루레이 수 vector<long long> lectures(N); long long lo = 0, hi = 0; for (int i = 0; i < N; i++) { //lo = 입력 값 중 최댓값, hi = 모든 강의 길이의 합 cin >> lectures[i]; hi += lectures[i]; lo = max(lo, lectures[i]); } long long mid, bluerays, lectureLen = 0; while (lo <= hi) { bluerays = 0, lectureLen = 0; long long mid = (lo + hi) / 2; for (int i = 0; i < N; i++) { if (lectureLen + lectures[i] > mid) { //만일 기준 강의 길이를 넘어간다 ? ++bluerays; //블루레이 추가 lectureLen = 0; //길이 초기화 } lectureLen += lectures[i]; } if (lectureLen != 0) ++bluerays; //마지막 예외처리 if (bluerays <= M) hi = mid - 1; //만일 입력 블루레이 수가 더 많거나 같으면 시간을 줄여서 블루레이 수를 늘려야함 else lo = mid + 1;//아니라면 시간 늘리기 } cout << lo; }