[1654번] 랜선 자르기

문제 출처 :

https://www.acmicpc.net/problem/1654

알고리즘 분석 :

문제 해결에 필요한 사항

1. 정렬

2. 이분 탐색(Binary Search)

나무 자르기 문제와 매우 유사하다. http://www.crocus.co.kr/522

랜선을 모두 정렬 한 후, 그에 따른 이분 탐색을 통해 cnt가 k보다 크거나 같은 값들을 

모두 save 배열에 저장 한 뒤, 마지막에 save를 정렬하여 가장 큰 값을 출력하도록 하면 된다.

소스 코드 : 

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

#include <iostream> #include <algorithm> #include <cstdio>   using namespace std;   long long int lan[1000001]; long long int save[1000001]; int s;   void binarySearch(long long int start, long long int end, int n, int k) {     long long int mid, cnt;       while (start <= end)     {         cnt = 0;         // 원하는 개수 보다 cnt가 크거나 같을 경우         // save 배열에 mid값을 저장한다.         // 모든 탐색을 끝내고 save 배열을 정렬하여 가장 큰 값을 출력시킨다.         mid = (start + end) / 2;           for (int i = 0; i < n; i++)             cnt += lan[i] / mid;           if (cnt >= k)         {                     save[s++] = mid;             start = mid + 1;         }           else             end = mid - 1;       } } int main() {     int n, k, res;       cin >> n >> k;       for (int i = 0; i < n; i++)         cin >> lan[i];       sort(lan, lan + n);       binarySearch(0, lan[n - 1], n, k);          sort(save, save + s);       cout <<    save[s - 1];       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus