[백준 1654번] 랜선자르기

이분탐색이 익숙치않아서 다시한번 풀어봤다.

K길이 최댓값에서 하나씩 감소시키는걸로 푸니 시간초과났었다.

굳이 sort해서 max값 안찾아도 되고, 입력받을때 max취해서 최대 K값 찾아놓고 시작하는게 나을것 같다.

괜히 시간만 잡아먹은듯.

 

#include <bits/stdc++.h>

using namespace std;

int N, K;
vector<int> vec;

bool check(int mid)
{
    int cnt = 0;
    for(int i = 0; i< K; i++)
    {
        cnt +=vec[i] /mid;
    }
    if(cnt >= N) return true;
    else return false;
}

int main(void)
{
    cin >> K >> N;
    long long sum = 0;
    for(int i = 0 ; i< K; i++)
    {
        int temp;
        cin >> temp;
        vec.push_back(temp);
    }
    sort(vec.begin(), vec.end());

    long long left, mid, right;
    left = 1;
    right = vec[vec.size()-1];
    mid = left+ (right-left)/2;
    long long result = 0;
    while(left <= right)
    {
        if(check(mid)) //return true;면 오른쪽 범위. 더 크게 잘라본다.
        {
            result = max(result, mid);
            left = mid+1;
        }else{ //return false면 왼쪽 범위. 더 작게 잘라본다.
            right = mid-1;
        }
        mid = left +(right-left)/2;
    }
    cout << result;
}

---

#include <bits/stdc++.h>

using namespace std;

int N, K;
vector<int> vec;

bool check(int mid)
{
    int cnt = 0;
    for(int i = 0; i< K; i++)
    {
        cnt +=vec[i] /mid;
    }
    if(cnt >= N) return true;
    else return false;
}

int main(void)
{
    long long left, mid, right=0;
    long long result = 0;
    
    cin >> K >> N;

    for(int i = 0 ; i< K; i++)
    {
        long long temp;
        cin >> temp;
        vec.push_back(temp);
        right = max(right, temp);
    }
    
    left = 1;
    mid = left+ (right-left)/2;
    while(left <= right)
    {
        if(check(mid)) //return true;면 오른쪽 범위. 더 크게 잘라본다.
        {
            result = max(result, mid);
            left = mid+1;
        }else{ //return false면 왼쪽 범위. 더 작게 잘라본다.
            right = mid-1;
        }
        mid = left +(right-left)/2;
    }
    cout << result;
}

이렇게 sort없이 했는데, 시간은 똑같았다.. 긁적;