1654번-랜선자르기

문제

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

1654번: 랜선 자르기

---

접근방법

분할하였을 때 랜선의 개수가 n개 이상으로 만들어야 하는 경우에 랜선의 길이를 최대로 결정해야 하는 문제였습니다. 그렇기 때문에 이 문제에서는 탐색을 해야 하는데 n의 개수가 10000개 이므로 최악의 경우 100,000,000번의 연산이 발생하게 되므로 시간초과가 발생하여 O(logn)으로 시간복잡도를 낮춰야 하는 문제였습니다. 그러므로 이분탐색을 활용하여 문제를 해결하는 방향으로 접근을 하였습니다.

---

정답코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 1e4 + 1;
ll arr[MAX];
int n, k;
 
int main(void)
{
    fastio;
    cin >> n >> k;
 
    ll highValue = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        highValue = max(highValue, arr[i]);
    }
//left는 1이상 부터의 조건이 있으므로 유의해야합니다.
    ll left = 1;
    ll right = highValue;
    ll ans;
    while (left <= right)
    {
        ll mid = (left + right) / 2;
 
        ll cnt = 0, sum = 0;
 
        for (int i = 0; i < n; i++)
            cnt += arr[i] / mid;
        
        if (cnt >= k)
        {
            left = mid + 1;
            ans = mid;
        }
        else
            right = mid - 1;
    }
    cout << ans << "\n";
}