접근

길이가 일정하지 않은 파를 샀는데 이것들을 사용해서 파닭에는 같은 양의 파를 넣어야한다. 그리고 남은 파를 라면에 넣어 먹으려고 하는데 그 파의 양을 구하는 문제이다.

파의 개수의 범위는 1<=S <= 1000000 이다. 그리고 주문 받은 파닭의 수는 1000000 이다.

먼저 만들어야할 파닭의 수가 있을것이다.
나는 그것을 기준을 두고 이분탐색으로 문제를 접근했다.

440,350,230 이 각각 파의 길이로 입력이 된다면 최소는 1 최대는 입력된 파의 길이중 최대값으로 정했다.(최소값으로 하면 최소값보다 큰값들의 파닭들이 기준으로 잡힐수가 없다)

그래서 최소값이 1 이라면 440+350+230 개의 파닭을 만들수 있을것이고, 230 이면 3개의 파닭을 만들수 있을것이다.

그래서 이 만들어진 파닭의 개수를 통해서 값을 늘려주고 줄여서 값을 찾는다.

하지만 우리의 문제는 파의 길이를 구하는 문제가 아니다.
결국 라면에 들어가는 파의 양을 구해야하기에 파닭에 들어가는 파의 양을 최대로 구하고 나머지를 구해주면 된다.

코드

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

int N,M;
long long low=1,high,mid,temp;
long long count_T,ret,tot;

vector<long long> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> N >> M;
    
    for(int i=0;i<N;i++) {
        cin >> temp;
        high=max(temp, high);
        v.push_back(temp);
    }
    
    while(low<=high) {
        mid=(low+high)/2;
//        cout << mid << "\n";
        count_T=0;
        
        for(long long a:v) {
            count_T+=(a/mid);
        }
        
        if(count_T<M) {
            high=mid-1;
        }
        else {
            ret=mid;
            low=mid+1;
        }
    }
    
//    cout << ret << "\n";
    
    for(long long a:v) {
        tot+=a;
    }
    cout << tot-(ret*M) << "\n";
    
    return 0;
}

틀린 이유

자꾸 생각을 잘못해서 high 에 입력받은 파닭중 최소값으로 정해서 틀렸다.
최소값으로 두어서 큰값들을 선택할려했는데 최대값으로 하고 최소값들을 선택안해도 그것들은 답이 될수 있기에 최대값으로 정해줬어야함