-
이진탐색 2 - Parametric Search, 백준 1654알고리즘 2024. 3. 2. 17:49
#include <iostream> using namespace std; int main(int argc, const char * argv[]) { cin.tie(NULL); ios::sync_with_stdio(false); int k, n; cin >> k >> n; int lines[k]; long start = 1, end = 0, mid = 0; for (int i = 0; i < k; i++) { cin >> lines[i]; if (end < lines[i]) { end = lines[i]; } } while (start <= end) { mid = (start + end) / 2; int count = 0; for (int i = 0; i < k; i++) { count += lines[i] / mid; } if (count >= n) { start = mid + 1; } else { end = mid - 1; } } cout << end; return 0; }
이진 탐색을 단순히 x 보다 큰지 작은지 말고, 다른 조건을 걸어두고
조건을 만족하는지, 아닌지로 범위를 좁혀나가 값을 찾아내는 방식입니다.
위 코드의 경우 조건을 만족하지 않으면 mid 숫자를 낮추고, 만족하면 mid 숫자를 높여서
조건을 만족하는 경우의 최대 크기 숫자를 구하는 코드입니다.
결국 "조건을 만족하는" "범위 내의 숫자" 라는 건 변함이 없지만,
이게 이진 탐색 문제인지 구분하는 것이 중요해 보입니다.
'알고리즘' 카테고리의 다른 글
스택 응용, 백준 9935: 문자열 폭발 (0) 2024.03.05 에라토스테네스의 체 (0) 2024.03.04 이분탐색 3 - LIS (Longest Increasing Subsequence), 백준 12105 (0) 2024.03.02 이분 탐색(binary search) (0) 2024.02.25