[ C++/ 백준 ] 보석 상자

2792번: 보석 상자

[ 아이디어 구상 ]

일단,, 문제가 이진 탐색이란걸 알고 선택한 문제여서 비교적 간단히 풀 수 있었다. 

백준에 공유기 설치 문제처럼 이진탐색이 어떤 특정 값을 찾는 데도 사용될 수 있다는 걸 알고 있던 상황이어서 그런 식으로 푸는거라는 걸 알 수 있었다. 

 

그래서 문제를 잘 읽어보고 눈에 띄는 조건 몇 개를 뽑았는데,

1. 색상 수가 정해져 있고 아이들 수, 색상 별 보석 갯수가 있다

2. 한 아이에게는 한 색상만 줄 수 있다 => 여기서 보석을 모두 합해서 구하는 건 불가능/ 그냥 나누기 하는건 안된단 거

3. 질투심은 보석을 가장 많이 받은 갯수다 => 최댓값만 찾으면 된다.

4. 보석을 못받는 아이가 있어도 된다. => 가장 많은 보석만 고려해보면 된다. 

5. 문제에는 안 적혀있었지만, 보석은 모두 소진해야한다. 

 

문제에 이 부분 때문에 가장 공정한 방법을 찾아야 하나? 했는데 그것도 아니었고 4번 조건을 보고 바로 

가장 많은 갯수의 보석을 골라서, 같은 개수( 또는 이하)로 나누어 줬을 때 보석을 모두 소진할 수 있는 방법이면 OK구나 라는 걸 알 수 있었다. 

 

그래서 

1. 가장 많은 보석 개수를 골라 이진 탐색으로 최소를 찾는다. 

2. 그 과정에서 모두 나누어 줄 수 있었다면 1, 아니면 0을 리턴

3. 1이 리턴 된다면 mid - 1을 해서 최솟값을 찾는다. 아니면 mid+1로 최댓값을 찾는다. 

4. ans 변수에 최소값을 기입한다. 

 

이런 동작 과정을 쓰면 되겠구나 알 수 있었다..! 

 

 

[코드]

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

using namespace std;

#define INF 2e9;

long long N, M;
int ans = INF;

int divide(int num, vector<int>& colors);

int main() {
	cin >> N >> M;
	vector<int> colors(M);

	for (int i = 0; i < M; i++) {
		cin >> colors[i];
	}
	sort(colors.begin(), colors.end()); // 오름차순 정렬
	int num = colors.back();
	int l = 0, r = num;
	while (l<=r) {
		int mid = (l + r) / 2;
		if (divide(mid, colors)) {
			r = mid - 1;
			ans = min(mid, ans);
		}
		else l = mid + 1;
	}
	cout << ans;
}

int divide(int num, vector<int> &colors) {
	if (!num) return 0;
	int jew = M - 1;
	long long available = 0;
	for (int i = 0; i < M; i++) {
		available += colors[i] % num?colors[i]/num+1:colors[i]/num;
	}
	if (available<=N) return 1;
	else return 0;
}

 

 

[주의할 점]

우선 입력 범위를 안 보고 진행했는데 N의 최대 범위가 10억이었다. 처음에 int로 했었는데 long long으로 급하게 변경...

그래서 for(i:0->N)로 보석 나눠줄 수 있는지 찾았는데 그것도 나누기로 바꿨음

 

 두번째로, 이진 탐색의 경우 보통은 배열과 같은 자료구조에서 값을 탐색하기 위한 알고리즘이기 때문에 0 인덱스가 포함된다. 근데 이번 문제처럼 최대 갯수를 찾는 경우에 + 나누기를 써서 풀게되는 경우에 0을 넣어주면 

제로 디비전이 되어버림,, 

실제로 96%? 쯤에 런타임 에러가 떠서 보니까 0으로 나눴기 때문이었음.