[백준/Baekjoon] 2343 기타레슨 C++ :: Binary search

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

2343번: 기타 레슨

---

1. Logic

이 문제에서는 이분탐색으로 찾으려는 mid값이 무엇인지를 정하는게 중요하다고 생각한다.

내가 정한 mid값은 블루레이의 길이이다.

 

강의 영상의 순서대로 블루레이에 넣어야되기 때문에 이분탐색의 check()함수는 블루레이에 순서대로 영상이 들어가는지 판단해주면 된다.

 

우리가 찾는 mid값은 가능한 값들중에 최솟값이기 때문에 가능한 mid값의 구간은 FFFF[FT]TTTT가 된다. 그중 가능한 값중 최솟값이기 때문에 end를 반환해주면 된다.

---

2. Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

long long n, m;
long long sum = 0;
vector<long long> course;

bool check(long long mid) {
    long long chSum = 0;
    long long cnt = 1;
    
    for(long long i = 0; i < n; i++) {
        if(course[i] <= mid) {
            chSum += course[i];
        }
        else return false;
        
        if(chSum + course[i+1] > mid) {
            if(cnt + 1 > m) return false;
            cnt++;
            chSum = 0;
        }
    }
    return true;
}

long long binarySearch() {
    long long start = 0;
    long long end = sum;
    long long mid;
    
    while(start + 1 < end) {
        mid = (start + end) / 2;
        
        if(check(mid)) end = mid;
        else start = mid;
    }
    
    return end;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        sum += a;
        course.push_back(a);
    }
    
    cout << binarySearch();
}

---

3. Feedback

이분탐색 진짜 이해했나?

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90