(백준 2805번 나무 자르기 C++) 라이님 블로그 대회 알고리즘 따라잡기 6) 이분탐색 2

라이님 블로그에 나와있는 풀이를 잘 익혀서 modern C++스타일로 짜봤다.

 

라이님 풀이는 아래 블로그 참고!

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

 

백준 2805번

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

2805번: 나무 자르기

 

최종적으로 chatgpt가 고쳐준 코드를 첨부해보았다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    
    vector<int> height(N);
    for (auto& h : height) {
        cin >> h;
    }
    
    int MAX_H = *max_element(height.begin(), height.end());

    auto getExcess = [&height, &M](int mid) -> long long {
        long long sum = 0;
        for (auto h : height) {
            if (h > mid) {
                sum += h - mid;
            }
        }
        return sum;
    };

    int lo = 0;
    int hi = MAX_H;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (getExcess(mid) >= M) {
            lo = mid;
        } else {
            hi = mid;
        }
    }

    cout << lo;
}

 

처음에 맞았습니다가 나왔을 때 메모리는 9836KB로 4년 전 풀이보다 메모리가 거의 2배이상 늘었었다.

 

그래서 chatgpt에게 두 코드의 차이점을 알려달라고 했고 chatgpt가 분석한 결과는 아래와 같다.

 

HolyMoly,,,

너무 똑똑하다!!!!!!!!!!!!!!!!!!!!!!!!

auto에서 함수 외부의 값을 참조 또는 복사할 때는 참조가 메모리 상에 이점이 훨씬 많다!!!ㅎㅎ

 

앞으로는 chatgpt가 알려준대로 auto함수에서 외부 값은 참조로 받는걸루...⭐