[BOJ] 백준 2792 보석상자

출처: https://www.acmicpc.net/problem/2792

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

[탐색] Parametric Search 

[탐색] Parametric Search

이분탐색을 통해서 최적의 질투심 수치를 찾습니다.

if) 질투심 수치를 『3』 이라고 했을 때 보석의 색상을 분배하는 방법은 다음과 같습니다.

    같은 색상의 보석을 분배하되 질투심 수치를 초과하지 않게 분배합니다.

 

Q) "RRRR"에서 3개를 넘지 않게 분배하는 방법을 어떤게 있을까?

    "R" + "R" + "R" + "R" / "RR" + "RR" / "RRR" + "R" / "RR" + "R" + "R"이 존재합니다. 

    ※ 보석을 받지 못하는 학생이 있어도 상관없기에 학생 수(N)만 충분하다면

       어떻게든 같은 색상을 나눠주기만 하면됩니다.

       하지만 학생 수(N)는 반드시 충분하지 않기 때문에 못받는 학생이 있더라도

       최대한으로 N을 아끼면서 보석을 분배합니다.

       따라서 3개를 초과하지 않는 선에서 나눠줍니다. → "RRR" + "R"

 

    ▶ 같은 색상의 보석 개수 X, 질투심 수치 Y인 경우 필요한 학생들의 수

        → X / Y + α (α 는 X%Y > 0 이면 1 아니면 0) 

        ex) "BBBBBBB" 보석 개수 = 7, 질투심 수치 = 3 → 7/3 + 1 = 3명 필요 → "BBB" + "BBB" + "B"

        → ((X-1) / Y) + 1로 대체 가능 → (7-1)/3 + 1 = 2 + 1 = 3

---

#include <stdio.h>
 
inline int max(int A, int B) { return A > B ? A : B; }
int N, M, cnt, maxVal = 0, arr[300001];
void input() {
    scanf("%d %d", &N, &M);
    register int i;
    for (i = 0; i < M; ++i) {
        scanf("%d", arr + i);
        maxVal = max(maxVal, arr[i]);
    }
}
 
int isPossible(int pivot) {
    cnt = 0;
    int i;
    for (i = 0; i < M; ++i) {
        cnt += (arr[i] - 1) / pivot + 1;
        // 구하는 과정에서 N명을 초과하는 경우
        if (cnt > N) return 0;
    }
    return 1;
}
 
int solve() {
    int start = 1, end = maxVal, mid, sol = 0;
    while (start <= end) {
        mid = (start + end) >> 1;
        if (isPossible(mid)) {
            sol = mid; end = mid - 1;
        }
        else {
            start = mid + 1;
        }
    }
    return sol;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    printf("%d\n", solve());
}