반응형 이분 탐색2 [C/C++] 백준 #2512 예산(이분 탐색) 이번 문제는 예산이 요청되었을 때, 정해진 예산에 맞추어 최대 허용 예산값을 구하는 문제입니다. https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이 문제는 최대 허용 예산값에 대해서 전체 예산 요청들을 만족하는지 아닌지를 판단할 수 있습니다. 최대 허용 예산값이 커질 수록 당연히 예산 초과가 될 수 있고, 최대 허용 예산값이 작아질수록 예산이 만족하기 때문에 어떤 값 이하에서는 항상 조건을 만족하고 그것을 초과하는 경우에는 항상 조건을 만.. 2023. 6. 12. [C/C++] 백준 #1654 랜선 자르기(이분 탐색) 랜선 자르기 문제는 K개의 랜선이 있을 때, 이 랜선을 적절히 잘라서 같은 길이의 N개의 랜선을 만드는 것입니다. 이 때, 가장 긴 길이의 N개의 랜선을 얻고자 할 때, 그 길이를 출력하는 것입니다. 이런 최적화 문제는 길이가 주어지면, K개의 랜선에서 N개의 랜선을 만들 수 있는지 검사하는 것은 어렵지 않다는 것입니다. 그리고 \( a \lt b \)를 만족하는 경우 b 길이가 가능하면 a 길이도 가능해야 문제를 풀 수 있습니다. 역으로 a 길이가 불가능하면 b 길이도 불가능해야 합니다. 그래야 이분 탐색을 이용하여 문제를 풀 수 있습니다. 4개의 랜선이 각각 길이가 802, 743, 457, 539 길이로 주어져있고, 이것으로 같은 길이의 11개 랜선을 요구한다고 합니다. \( K \le N \)이므.. 2022. 9. 22. 이전 1 다음 728x90
