[백준] 2792. 보석 상자 - C++

문제

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

 

• 소요 시간 : 1시간
• 난이도 : 실버 2

접근 방법

1차 (틀린 풀이)

M을 N개로 나누는 과정이라고 생각을 해보았었다.

 

ex. N = 5, M = 2 (7, 4)

M = 2 -> 3개로 만들기 위해 
가장 큰 수인 7을 반으로 나눈다. 
7, 4 -> 3, 4, 4

M = 3 -> 4개로 만들기 위해
가장 큰 수인 4를 반으로 나눈다. 
 3, 4, 4 -> 3, 2, 2, 4

M = 4 -> 5개로 만들기 위해
가장 큰 수인 4를 반으로 나눈다. 
3, 2, 2, 4 -> 3, 2, 2, 2, 2

 

이때 가장 큰 값(3)이 질투심이라고 생각했다.

하지만 이 방법은 N값의 범위가 최대 10억이기 때문에 시간초과가 난다.

2차 

질투심에 초점을 맞추었다. 

질투심이 n일때 나눠지는 덩어리의 수가 학생의 수(N)보다 작거나 같으면 된다. 

이때 최소가 되는 질투심을 구하기 위해 이분탐색을 사용한다.

최솟값은 1, 

최댓값은 가장 많은 개수를 가진 색상의 개수로 설정한다. (한 학생은 한 색상만 가질 수 있으므로)

 

나눠지는 덩어리의 수가 학생의 수(N)보다 작다면 더 잘게 쪼개야하므로 질투심을 더 작게 설정해야한다. 

나눠지는 덩어리의 수가 학생의 수(N)보다 크다면 더 크게 쪼개야하므로 질투심을 더 크게 설정해야한다. 

 

ex. N = 5, M = 2 (7, 4) 일때 예시를 들면 아래 그림과 같이 찾아나간다.

 

 

나의 풀이

1차

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;



pair<long long, long long> divideHalf(long long num) {
    if (num % 2 == 0) {
        return {num/2, num/2};
    } else {
        return {(num-1)/2, ((num-1)/2)+1};
    }
}

int main() {
    long long N;
    int M;

    cin >> N >> M;

    long long cnt;
    vector<long long> v;

    for(int i=0; i<M; i++) {
        cin >> cnt;
        v.push_back(cnt);
    }

    // 10억번 돌게될 수도..?!
    while(v.size() != N) {
        sort(v.begin(), v.end());

        long long biggest = v.back();
        v.pop_back();

        pair<long long, long long> p = divideHalf(biggest);

        v.push_back(p.first);
        v.push_back(p.second);
    }

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

    cout << v[v.size()-1];
    
    return 0;
}

 

결과 : 시간초과

2차 

#include <iostream>
#include <vector>
#include <algorithm>

typedef long long ll;

using namespace std;

vector<ll> v;
ll N;


bool check(ll jealousy) {
    // 모든 색상을 질투심으로 나눴을 때의 개수
    ll cnt = 0;
    for(ll color : v) {
        if (color % jealousy == 0)
            cnt += color / jealousy;
        else 
            cnt += (color / jealousy) + 1;
    }

    return N >= cnt;
}

int main() {

    // input
    int M;

    cin >> N >> M;


    ll cnt;
    for(int i=0; i<M; i++) {
        cin >> cnt;
        v.push_back(cnt);
    }

    // solve 
    ll left = 1, right = *max_element(v.begin(), v.end());
    ll mid;
    ll answer = 1e18;

    while(left <= right) {
        mid = (left + right) / 2;
        if (check(mid)) {
            answer = min(answer, mid); 
            right = mid - 1;
        } else
            left = mid + 1;
    } 
     

    cout << answer;

    return 0;
}

 

결과 : 정답

정리

문제의 초점이 질투심을 낮추는 것이니까 이것에 맞춰서 알고리즘을 생각해봐야겠다.