[백준] 14627번 파닭파닭 - C++

14627번: 파닭파닭

문제

평소 요리에 관심이 많은 승균이는 치킨집을 개업하였다. 승균이네 치킨집은 파닭이 주메뉴다. 승균이는 가게를 오픈하기 전에 남부시장에 들러서 길이가 일정하지 않은 파를 여러 개 구매하였다. 승균이는 파닭의 일정한 맛을 유지하기 위해 각각의 파닭에 같은 양의 파를 넣는다. 또 파닭 맛은 파의 양에 따라 좌우된다고 생각하기 때문에 될 수 있는 한 파의 양을 최대한 많이 넣으려고 한다. (하지만 하나의 파닭에는 하나 이상의 파가 들어가면 안 된다.) 힘든 하루를 마치고 승균이는 파닭을 만들고 남은 파를 라면에 넣어 먹으려고 한다. 이때 라면에 넣을 파의 양을 구하는 프로그램을 작성하시오. 승균이네 치킨집 자는 정수만 표현되기 때문에 정수의 크기로만 자를 수 있다.

입력

첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에 걸쳐 파의 길이 L(1 ≤ L ≤ 1,000,000,000)이 정수로 입력된다.

출력

승균이가 라면에 넣을 파의 양을 출력한다.

예제 입력 1

3 5
440
350
230

예제 출력 1

145

힌트

파닭 하나당 넣을 수 있는 최대 파의 길이는 175cm으로, 440cm 파에서 2개, 350cm 파에서 2개, 230cm 파에서 1개, 총 5개의 파닭을 만들 수 있고, 각각의 파에서 90cm + 0cm + 55cm = 145cm의 파가 남는다.

---

문제 요약

입력받은 길이가 다른 파들의 최대 파 길이를 찾아 C개의 파닭을 만들고 남은 파의 길이를 구하기

생각할 점

• C개의 파닭을 전부 만들 수 있는 파의 길이를 이진 탐색으로 찾고 그 때 각 파에서 얼만큼의 길이가 남는지를 구한다.
• 파닭 하나당 넣을 수 있는 최대 파의 길이를 이진탐색으로 찾고
• 전체 파 길이를 구해서 ( 최대파 길이 * 치킨 수 )를 빼준다.

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

int main(){
    
    long long S, C; 
    cin >> S >>C;
    vector<long long> L(S);
    for(int i = 0; i < S; i++){
      cin >> L[i];  
    } 
    
    long long min = 1;
    long long max = 1e9;
    long long total = 0;
    long long maxPa = 0;
    
    while(min <= max){
        long long mid = (min + max) / 2;
        long long sum = 0;
        for(int i=0; i < L.size(); i++){
            if(L[i] >= mid) 
                sum += L[i] / mid;
        }
        if(sum >= C){
            maxPa = mid;
            min = mid + 1;
        }
        else 
            max = mid - 1;
    }
    
    for(int i=0; i<L.size(); i++){
       total += L[i];
    } 
        
    cout<< total - maxPa * C << endl;
}

주석 버전

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

int main(){
    //S는 파의 수, C는 만들 파닭의 수
    long long S, C; 
    cin >> S >>C;
		//파들의 길이를 저장할 벡터 L
    vector<long long> L(S);
    for(int i = 0; i < S; i++){
      cin >> L[i];  
    } 
    //파의 최소 길이
    long long min = 1;
		//파의 최대 길이 (파 길이의 범위가 1~10의 9승임)
    long long max = 1e9;
		//전체 파길이
    long long total = 0;
		//파닭 하나 당 들어가는 최대 파의 길이
    long long maxPa = 0;
    
    while(min <= max){
				//C개의 파닭을 만들기 위해 탐색할 파 길이의 중간값
        long long mid = (min + max) / 2;
				//만들 수 있는 파닭의 수
        long long sum = 0;

				//파길이들을 mid로 나누면 최대 파길이가 mid일 때 만들 수 있는 
				//파닭의 수를 구할 수 있다.
        for(int i=0; i < L.size(); i++){
            if(L[i] >= mid) 
                sum += L[i] / mid;
        }
				//C개의 파닭을 만들 수 있으면 최대 파길이 maxPa가 mid이거나
				//mid 보다 크다.
        if(sum >= C){
            maxPa = mid;
            min = mid + 1;
        }
				//C개의 파닭을 만들 수 없으면 탐색 범위가 잘못된 경우다.
        else 
            max = mid - 1;
    }
    //전체 파길이의 합 total
    for(int i=0; i<L.size(); i++){
       total += L[i];
    } 
    //전체 파길이의 합 - 최대 파길이 * 파닭 수   
    cout<< total - maxPa * C << endl;
}