Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 컴퓨터공학과
- 그래프
- bfs
- 스택
- Operating System
- 구현
- vector
- 정석
- cs
- 문제풀이
- 정석학술정보관
- 너비우선탐색
- 컴공
- 오퍼레이팅시스템
- 백준
- DP
- 오에스
- 북리뷰
- Computer science
- 컴공과
- 브루트포스
- 코딩
- 자료구조
- 알고리즘
- Stack
- 코테
- coding
- 개발
- c++
- OS
Archives
- Today
- Total
Little Jay
[C++] 백준 2512번 - 예산 본문
이진탐색을 활용하는 문제
생각보다 이진탐색할때 조건을 설정하는 부분이 어려웠다
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long arr[10001];
int main() {
int n, sum = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
sum += arr[i];
}
int budget;
cin >> budget;
sort(arr, arr + n);
long long low = 0;
long long high = arr[n - 1];
if (sum <= budget) {
cout << arr[n - 1] << '\n';
}
else {
while (low + 1< high) {
long long mid = (low + high) / 2;
long long temp_budget = 0;
for (int i = 0; i < n; i++) {
if (arr[i] >= mid) {
temp_budget += mid;
}
else
temp_budget += arr[i];
}
if (temp_budget > budget) {
high = mid;
}
else if (temp_budget <= budget) {
low = mid;
}
}
cout << low << '\n';
}
return 0;
}
'알고리즘 > BOJ' 카테고리의 다른 글
[C++] 백준 1110번 - 더하기 사이클 (0) | 2021.09.03 |
---|---|
[C++] 백준 1789번 - 수들의 합 (0) | 2021.09.02 |
[C++] 백준 5622번 - 다이얼 (0) | 2021.09.02 |
[C++] 백준 1149번 - RGB거리 (0) | 2021.08.30 |
[C++] 백준 6443번 - 애너그램 (0) | 2021.08.25 |
Comments