[백준/C++] 14627번: 파닭파닭

문제 & 링크

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

풀이

1. 하나의 파닭에 넣을 수 있는 최대의 파의 길이, 즉 최적의 해를 구하기 위해 파라메트릭 서치를 사용한다.

2. 파닭에 넣은 수 있는 파의 최소 길이는 1, 최대 길이는 제일 긴 파의 길이이다.

3. 이분탐색을 활용하여 mid 값이 조건(mid 길이로 설정했을 때 모든 파닭에 파를 줄 수 있는지)을 만족하는지 확인한다.

4. 만약 true일 경우 더 긴 길이의 파를 주어도 조건을 만족하는지 확인하기 위해 left = mid + 1을 해준다.

5. 만약 false일 경우 더 짧은 길이의 파는 조건을 만족하는지 확인하기 위해 right = mid - 1을 해준다.

6. left > right가 될 경우 반복문은 종료되고, 모든 파닭에 파를 줄 수 있는 파의 최대 길이가 나온다.

7. 남은 파를 라면에 넣을 것이기에, 전체 파의 길이에서 위에서 구한 파의 길이 * 파닭의 개수를 빼주면 답을 구할 수 있다.

코드

#include <iostream>
#include <vector>

using namespace std;

int S, C;
vector<int> V;

bool parametric_search(int value) {
    long long cnt = 0;
    for (int i = 0; i < S; i++) {
        cnt += V[i] / value;
    }

    return cnt >= C;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> S >> C;

    V = vector<int>(S);

    long long sum = 0;
    int right_value = 0;  

    for (int i = 0; i < S; i++) {
        cin >> V[i];

        right_value = max(right_value, V[i]);
        sum += V[i];
    }

    int left = 1, right = right_value;
    int mid;
    int max_input = 0;
    while (left <= right) {
        mid = (left + right) / 2;

        if (parametric_search(mid)) {
            max_input = mid;
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    long long ans = sum - (long long)max_input * C;

    cout << ans;
}