(백준 2512번 예산 C++) 라이님 블로그 대회 알고리즘 따라잡기 6) 이분탐색 1

Modern C++과 함께 하는 월요일 아침.. 이분탐색 코드도 Modern C++ Style로 짜보기로 마음 먹었다.

참고로 이번주는 이분탐색을 뽀갤 예정!!

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220777333252&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

이분 탐색(Binary Search) (수정 2019-02-15)

 

백준 2512번

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

2512번: 예산

 

원래는 입력을 <cstdio>에 있는 scanf를 사용했는데, 문뜩 <iostream>의 cin의 성능을 높일 수는 없는가 생각이 들었다.

(scanf가 cin보다 약 3배정도 빠르다!)

 

https://velog.io/@matcha_/%EB%B0%B1%EC%A4%80-C-cin-cout-%EC%9E%85%EC%B6%9C%EB%A0%A5-%EC%86%8D%EB%8F%84-%EB%B9%A0%EB%A5%B4%EA%B2%8C-%ED%95%98%EB%8A%94-%EB%B2%95

[백준] C++ cin, cout 입출력 속도 빠르게 하는 법

헤헤 없을리가! 이유는 위 블로그를 참고!!

 

ios_base::sync_with_stdio(false);

※ 1. C의 입출력 방식과 동시 사용 불가 2. 멀티쓰레드 불가

cin.tie(NULL);

⭐ endl보다 "\n"이 더 빠르다!

 

auto와 lambda함수, 그리고 vector를 이용해보았다.(많은 부분을 chatgpt가 알려줬다..ㅎㅎ)

//2512번 
#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int N, M, MAX_B;
    cin >> N;

    vector<int> budget(N);
    for (auto& b : budget) cin >> b;
    MAX_B = * max_element(budget.begin(), budget.end());

    cin >> M;

    auto getTotal = [&M, budget](int mid) {
        long long sum = 0;
        for (const auto& b : budget) {
            if (b > mid) sum += mid;
            else sum += b;
        }
        return sum;
    };

    int lo = 1, hi = MAX_B;

    if (getTotal(hi) <= M) { cout << hi;  return 0; }

    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (getTotal(mid) <= M) lo = mid;
        else hi = mid;
    }

    cout << lo;
    return 0;
   
}

 

처음에 실수한 부분이 lo와 hi부분인데, [lo, hi)인 만큼 출력은 lo로 해주되 if문 안에서 lo와hi를 mid로 업데이트해줄 때 lo를 기준으로 해주면 된다!!!

 

C++ 20 껄껄

 

저번주에 급하게 배운 modern C++을 코드에 써먹다니.. 씬난당