[백준,c++] 2792번 - 보석 상자

문제

2792번: 보석 상자

 

코드

#include <iostream>
#include <vector>
#define ll unsigned long long int
using namespace std;

int N, M;
vector<ll> v;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>M;
    ll max_find = 0;
    for(int i=0; i<M; i++){
        int inp; cin>>inp;
        v.push_back(inp);
        max_find += inp;
    }
    
    ll start = 1, end = max_find;
    ll ans = 0;
    while(start <= end){
        ll mid = (start + end) / 2;
        ll jeal = mid;  // 최대 질투심
        ll peo = 0;
        for(int i=0; i<M; i++){
            if(jeal >= v[i]) peo += 1;
            else{
                if(v[i] % jeal == 0) peo += v[i] / jeal;
                else peo += (v[i] / jeal) + 1;
            }
        }
        if(peo > N) start = mid +1;
        else{
            ans = mid;
            end = mid -1;
        }
    }
    cout<<ans;
    
}

 

풀이

[백준,c++] 6236번 - 용돈 관리

위 문제와 거의 유사합니다.

최대 질투심을 유발하는 개수를 이분 탐색을 통해서 정한 후에 해당 질투심을 가지고 모든 보석을 탐색합니다.

해당 보석의 갯수가 질투심을 유발하는 개수보다 작다면 그냥 전부 나눠줍니다. 

만약 보석의 갯수가 질투심을 유발하는 개수보다 클 때

• (보석 % 질투심) == 0 이라면 전부 질투심 개수만큼 나눠줄 수 있으니 나눠주고,
• (보석 % 질투심) != 0이라면 한 명은 질투심보다 적은 개수를 받게 될 테니 인원의 수를 추가로 +1 해줍니다.

최종적으로 보석을 나눠준 인원의 수 > N일 경우에 질투심을 유발하는 수를 더 크게 세팅하여 탐색하고 반대의 경우에는 더 작게 세팅하여 탐색합니다.

예제 입출력 2를 예를 들어 살펴보면 다음과 같습니다.

7 5
7
1
7
4
4

 

1 4 4 7 7 만큼의 보석 갯수가 있고, 질투심을 유발하는 개수가 4라면 아래와 같이 나눠줄 수 있습니다.

각 보석의 갯수	1	4	4	7	7
나눠준 보석의 갯수	1	4	4	4, 3	4, 3