[ 백준 14233 ] 악덕 사장 (c/c++)

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

 

 

[ 문제 요약 ]

N개의 일의 마감 기한이 주어질 때, 각 작업마다 동일한 시간 k을 할당하여 가능한 한 최대의 시간을 출력한다.

 

 

[ 문제 풀이 ]

1. 우선 일이 정렬되어 주어지지 않기 때문에 정렬한다.

2. 만약 어떤 일에 주어진 시간 k와 일을 할 수 있는 일 수 i에 대하여 k * i가 주어진 마감 기한보다 크다면 그 일은 할 수 없는 일이 된다.

3. k를 분할 정복을 통해서 구하되 k가 정해질 때마다 위 방식으로 계속 확인하여 모든 일을 할 수 있는 최대값을 찾는다.

 

 

[ 문제 풀이 ]

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

int N;
vector<int> v;

bool can(int k) {
    for (int i = 0; i<v.size(); i++) {
        if (k * (i + 1) > v[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> N;
    
    for (int i=0; i<N; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }

    sort(v.begin(), v.end());

    int low = 1, high = 1000000000;
    int max_k = 0;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (can(mid)) {
            max_k = mid;
            low = mid + 1;
        } else high = mid - 1;
    }

    cout << max_k;

    return 0;
}

 

 

[ 주의할 점 ]

문제를 이해하는 데 조금 어려웠다.