[백준 16401번] 과자 나눠주기 (C++)

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

16401번: 과자 나눠주기

---

과자 나눠주기 문제는 Parametric Search를 이용하여 해결할 수 있습니다. 

Parametric Search는 최적화 문제를 결정 문제로 변환해 이분탐색을 수행하는 방법을 의미합니다. - [바킹독의 실전 알고리즘] 이분탐색

 

조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하는 문제(최적화 문제)에서 

조카 1명에게 줄 수 있는 막대 과자의 길이가 L일 때, 조카 M명에게 과자를 모두 동일하게 나누어줄 수 있는가?(결정 문제)

 

증가함수이거나 감소함수 일때, Parametric Search를 사용할 수 있습니다. 

조카 1명에게 주는 과자의 길이를 늘리면, 과자를 줄 수 있는 조카의 수가 줄어듭니다.

따라서 막대과자의 길이(L)에 대한 나누어 줄 수 있는 조카의 수(M)의 함수는 감소함수이므로 Parametric Search를 사용할 수 있습니다. 

 

알고리즘은 아래와 같습니다.

• 탐색 범위는 low ~ high
• 과자의 길이 = mid = (low + high + 1) / 2
• 나누어 줄 수 있는 조카가 M명 이상이면, 탐색 범위를 mid ~ high로 변경
• 나누어 줄 수 있는 조카가 M명 미만이면, 탐색 범위를 low ~ (mid - 1)로 변경

 

아래는 전체 코드입니다.

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

int snack[1000010];
int m, n; 
long long snack_length(int L){    // 조카 1명에게 줄 막대 과자의 길이가 X일 때, 과자를 줄 수 있는 조카의 수를 반환
    long long sum = 0;
    for(int i = 0; i < n; i++)
        sum += snack[i] / L;
    return sum;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> m >> n;
    for(int i = 0; i < n; i++) cin >> snack[i];

    int high = *max_element(snack, snack + n);
    int low = 1;
    while(low < high){
        int mid = (high + low + 1) / 2;
        if(snack_length(mid) >= m){  // 더 많은 조카들에게 나누어줄 수 있는 경우
            low = mid;  // 과자의 길이를 늘림
        }else if(snack_length(mid) < m){
            high = mid - 1; // 과자의 길이를 줄임
        }
    }

    int length = (high + low) / 2;
    if(snack_length(length) >= m) cout << length << "\n"; // 길이가 length인 과자들 M명 이상에게 나누어줄 수 있는 경우 
    else cout << 0 << "\n"; // 과자를 M명에게 나누어 줄 수 없는 경우
}

 

아래는 문제 풀이에 사용된 테스트케이스입니다.

1 4
1 1000000000 1000000000 1000000000
-> 1000000000