백준 2792 [C++]

www.acmicpc.net/problem/2792

2792번: 보석 상자

1. 풀이방법

 

- 구현 문제를 많이 풀다보니 이런문제를 처음 봤을 때, 조금 당황스러웠습니다...;

 

- 어쨋든 최소질투심을 유발하게끔 나눠주는 방법은 1과 최대보석의 수 중에 있을 것이니까

 

- 이분 탐색을 통해 그것을 탐색해가면서 mid의 값이 아이들에게 조건에 맞게 나누어 줄 수 있는지 확인.

 

- 나누어 줄 수 있으면 더 작은 질투심을 유발할 수 있는 값이 있는지 mid보다 작은 쪽을 탐색.

 

- 아니라면 mid보다 큰 쪽을 탐색.

 

- 최소값을 출력하여 주었습니다.

 

 

2. 주의사항

 

- 없음.

 

 

3. 나의코드

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

long long n, m;
long long numarr[300001];
long long result = 1e18;

bool canspread(long long mid) {
    long long num = 0;
    for (int i = 0; i < m; i++) {
        num += numarr[i] / mid;
        if (numarr[i] % mid) num++;
    }
    return n >= num;
}
int main() {
    cin >> n >> m;
    long long left = 1; long long right = 0;
    for (int i = 0; i < m; i++) {
        cin >> numarr[i];
        if (right < numarr[i]) right = numarr[i];
        }
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (canspread(mid)) {
            if (result > mid) result = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }
    cout << result << "\n";
    return 0;
}