경우없는 개발 블로그

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

#문제 간단 정리

이분 탐색을 사용하는 문제

#문제 해결 방법

이분탐색으로 입력된 길이중 가장 긴 랜선을 max 로 잡고

탐색할때마다 mid 를 각 랜선들을 잘랐을때 

자른 개수가 N개 이상이 되면 mid 를 점점 올리면서 이분 탐색을 해서 최대 길이로 자를 수 있는 값을 구한다.

#전체 코드

C++ 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int arrK[1000000] = { 0, };
int cnt[1000000] = { 0, };
int n, k;

//int mod(int length) {
//    int count = 0;
//    for (int i = 0; i < k; i++) {
//        cnt[i] = arrK[i] / length;
//        count += cnt[i];
//    }
//    if (count >= n) {
//        return length;
//    }
//    else {
//        return -1;
//    }
//}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> k >> n;
    int kmax = -1;
    for (int i = 0; i < k; i++) {
        cin >> arrK[i];
        kmax = max(kmax, arrK[i]);
    }

    long long left = 1;
    long long right = kmax;
    int result = -1;
    while (left <= right){
        long long mid = (left + right) / 2;
        int count = 0;
        
        for (int i = 0; i < k; i++) {
            count += arrK[i] / mid;
        }
        
        if (count >= n) {
            left = mid + 1;
            if (result < mid) result = mid;
        }
        else {
            right = mid - 1;
        }
    }
    
    cout << result;
    return 0;
}

python 풀이

K,N = map(int,input().split())
Data = []
maxH = 0
maxN = 0
def cutting(mid):
    counting = 0
    for i in range(len(Data)):
        counting += Data[i] // mid

    return counting

for  i in range(int(K)):
    height = int(input())
    Data.append(height)
    maxH = max(maxH,Data[-1])

Data.sort()

start = 1; end = maxH
mid = (end+start)//2


while start <= end:
    mid = (end + start) // 2
    now = cutting(mid)
    if now >= N:
        start = mid + 1
        maxN = mid
    elif now < N:
        end = mid -1


print(maxN)