[틀림] 백준 14627 파닭파닭 // 매개변수탐색, 나머지 구하기

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

* 풀이

• 어려웠던점
  • 각각 원소에대해 순회하면서 나머지를 더하는 방식의 문제
  • 아래의 경우, 답이 0이 되어버림

• 개선
  • 순회대신, sum을 구하고
  • 파길이의 전체합(sum) - (최적의파갯수 * 주문받은 파닭수) 하면 됨
  • sum - (ret*c)를 출력 하면 됨.
  • ex) 1020 - ( 175 * 5 ) = 145

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

ll ret, s,c;
ll a[1000000+4];

int go(ll x) {
   ll cnt=0;
   for(int i=0;i<s;++i) {
      cnt+=a[i]/x;
   }
   return cnt>=c;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   cin>>s>>c;
   ll sum=0;
   for(int i=0;i<s;++i) {
      cin>>a[i];
      sum+=a[i];
   }

   ll st=0;
   ll en=INT_MAX;
   while(st<=en) {
      ll mid = (st+en)/2;
      if(go(mid)) {
         ret=mid;
         st=mid+1;
      }
      else {
         en=mid-1;
      }
   }

   // cout<<ret<<"\n"; // 최적의 파닭갯수
   // ll res=0;
   // ll cnt=0; //만든 파닭의 갯수
   // for(int i=0;i<s;++i) {
   //    cnt+=a[i]/ret;
   //    res+=a[i]%ret;
   //    
   // }
   // if(cnt>ret) {
   //    ll gab = cnt-ret;
   //    res+=gab*ret;
   // }
   // // res += sum-ret*c; // 사용하지 않는 부분 더해줘야함
   // cout<<res;
   cout<<sum-ret*c;
}