[백준,c++] 14627번 - 파닭파닭

문제

14627번: 파닭파닭

 

코드

#include <iostream>
#include <vector>

#define ll long long int
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ll S, C; cin>>S>>C;
    vector<ll> v(S);
    for(int i=0; i<S; i++) cin>>v[i];
    
    ll start = 1, end = 1e9;
    ll mod = 0, sum = 0;
    
    while(start <= end){
        ll mid = (start + end) / 2;
        ll sum = 0;
        for(int i=0; i<v.size(); i++){
            if(v[i] >= mid) sum += v[i] / mid;
        }
        if(sum >= C){
            mod = mid;
            start = mid + 1;
        }
        else end = mid - 1;
    }
    
    for(int i=0; i<v.size(); i++) sum += v[i];
    cout<< sum - mod * C;
}

 

풀이

파닭 하나당 넣을 수 있는 최대 파의 길이를 이분 탐색을 통해서 정해줍니다. 정한 파의 길이를 계속 이분 탐색을 통해 갱신하고, 최종적으로 (모든 파의 양) - (닭 개수 * 파닭 하나당 넣을 수 있는 최대 파의 길이)를 빼주면 정답이 됩니다.