-
(백준 2512번 예산 C++) 라이님 블로그 대회 알고리즘 따라잡기 6) 이분탐색 1PROGRAMMING/알고리즘 2024. 3. 18. 08:46
Modern C++과 함께 하는 월요일 아침.. 이분탐색 코드도 Modern C++ Style로 짜보기로 마음 먹었다.
참고로 이번주는 이분탐색을 뽀갤 예정!!
이분 탐색(Binary Search) (수정 2019-02-15)
안녕하세요. 블로그 점검이 새벽 1시부터 시작되어서 아쉽게도 개삘인 오늘 달릴 수가 없네요. 하지만...
blog.naver.com
백준 2512번
https://www.acmicpc.net/problem/2512
2512번: 예산
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상
www.acmicpc.net
원래는 입력을 <cstdio>에 있는 scanf를 사용했는데, 문뜩 <iostream>의 cin의 성능을 높일 수는 없는가 생각이 들었다.
(scanf가 cin보다 약 3배정도 빠르다!)
[백준] C++ cin, cout 입출력 속도 빠르게 하는 법
나는 C++을 이용해서 백준 문제를 풀고있다. 그런데 풀다가 이상한 광경을 목격했다. 다른 사람의 코드를 봤는데, 분명 나와 코드 구조는 같은데 실행 시간이 훨씬 빨랐다. 뭐가 다른걸까 비교해
velog.io
헤헤 없을리가! 이유는 위 블로그를 참고!!
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++을 코드에 써먹다니.. 씬난당
'PROGRAMMING > 알고리즘' 카테고리의 다른 글