나무 자르기
-
[백준] 2805번 나무 자르기알고리즘/백준 2021. 8. 29. 16:49
문제 링크 풀이 내가 가져갈 수 있는 나무 길이가 나오는, 나무의 절단 높이를 구하는 문제다. 20 높이의 나무의 15로 높이로 절단하면 5를 가져간다. 이 문제의 특성은 이분 탐색을 통해 절단 높이를 구해가는 과정에서, 절단 높이가 작아질수록 잘린 나무의 길이가 커지는 데 있다. 그러므로 일반적인 이분 탐색에서 high, low를 구하는 조건을 반대로 해주면 된다. 코드 #include #include using namespace std; // 2805번 int main() { int N; // 나무 수 scanf("%d", &N); vector trees(N); long long M; // 필요한 나무의 길이 long long answer = 0; // 절단기에 설정할 최대 높이 long long h..