득이공간
[백준 C++] 2805 나무 자르기 - 이분탐색 본문
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int N, M;
cin >> N >> M;
vector<int> Trees;
Trees.reserve(N);
for (int i = 0; i < N; ++i)
{
int Tree;
cin >> Tree;
Trees.emplace_back(Tree);
}
int Result = 0;
int Height = 0;
int MinHeight = 0;
int MaxHeight = *max_element(Trees.begin(), Trees.end());
while (MinHeight <= MaxHeight)
{
Height = (MinHeight + MaxHeight) / 2;
long long Sum = 0;
for (const int& Tree : Trees)
{
if (Tree > Height)
{
Sum += Tree - Height;
}
}
if (Sum < M)
{
MaxHeight = Height - 1;
}
else
{
Result = Height;
MinHeight = Height + 1;
}
}
cout << Result;
}
높이의 범위를 좁혀가며 이분 탐색하도록 할 때
조건을 어떻게 잡느냐에 따라서
시간초과 발생 유무가 있습니다.
그리고 M의 범위가 (1 ≤ M ≤ 2,000,000,000)이므로
Sum의 자료형 선택에도 주의가 필요합니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 14501 퇴사 - 브루트포스 (1) | 2024.01.30 |
---|---|
[백준 C++] 1654 랜선 자르기 - 이분탐색 (1) | 2024.01.29 |
[백준 C++] 2108 통계학 - 정렬 (1) | 2024.01.28 |
[백준 C++] 2178 미로 탐색 - 너비우선탐색 (1) | 2024.01.28 |
[백준 C++] 1260 DFS와 BFS - 깊이우선탐색, 너비우선탐색 (0) | 2024.01.25 |