[BOJ] 보석 μƒμž(2792)

[λ°±μ€€(BOJ)] 보석 μƒμž(2792) C++

문제 : BOJ_2792번 보석 μƒμž

문제 μ„€λͺ…

이뢄탐색

이뢄 νƒμƒ‰μœΌλ‘œ ν•΄κ²°ν•  수 μžˆλŠ” λ¬Έμ œμž…λ‹ˆλ‹€.
μ‚¬λžŒ 수 N이 있고, λ³΄μ„μ˜ μ’…λ₯˜ 수 M이 μžˆμŠ΅λ‹ˆλ‹€.
ν•œ μ‚¬λžŒμ—κ²ŒλŠ” ν•œ μ’…λ₯˜μ˜ 보석을 λ‚˜λˆ  쀄 수 있고, λͺ¨λ“  μ‚¬λžŒμ—κ²Œ 보석을 쀄 ν•„μš”λŠ” μ—†μ§€λ§Œ, λͺ¨λ“  보석은 λ‚˜λˆ„μ–΄μ€˜μ•Ό ν•©λ‹ˆλ‹€.
μ΄λ•Œ, 보석을 κ°€μž₯ 많이 κ°–κ³  μžˆλŠ” μ‚¬λžŒμ˜ 보석 수λ₯Ό μ§ˆνˆ¬μ‹¬μ΄λΌκ³  ν•  λ•Œ, μ§ˆνˆ¬μ‹¬μ˜ μ΅œμ†Ÿκ°’μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€.


Solution

μ§ˆνˆ¬μ‹¬μ„ μ΅œμ†Œλ‘œ ν•˜λ €λ©΄, λ³΄μ„μ˜ μ’…λ₯˜μ™€ 상관없이, N λͺ…이 λ„˜μ–΄κ°€μ§€ μ•ŠμœΌλ©΄μ„œ, ν•œ ν•™μƒμ—κ²Œ λ‚˜λˆ„μ–΄μ€„ 수 μžˆλŠ” λ³΄μ„μ˜ 수의 μ΅œμ†Ÿκ°’μ„ ꡬ해야 ν•©λ‹ˆλ‹€.
κ·ΈλŸ¬λ―€λ‘œ, 보석 수λ₯Ό μ¦κ°€μ‹œν‚€λ©΄μ„œ, λͺ¨λ“  보석을 Nλͺ… μ΄ν•˜μ˜ ν•™μƒμ—κ²Œ λ‚˜λˆ μ€„ 수 μžˆλŠ”μ§€λ₯Ό 이뢄 탐색을 톡해 μ°Ύμ•„μ•Ό ν•©λ‹ˆλ‹€.
μ΄λ ‡κ²Œ 찾은 λ‚˜λˆ μ£ΌλŠ” 보석 μˆ˜κ°€ μ΅œμ†Œμ˜ μ§ˆνˆ¬μ‹¬μ΄ λ©λ‹ˆλ‹€.


Description

Nλͺ…을 계산할 λ•Œ, λ³΄μ„μ˜ μˆ˜μ™€ λ‚˜λˆ μ£ΌλŠ” λ³΄μ„μ˜ μˆ˜κ°€ λ‚˜λˆ„μ–΄λ–¨μ–΄μ§€μ§€ μ•ŠλŠ”λ‹€λ©΄, μΉ΄μš΄νŠΈμ— 1을 더해주어야 ν•©λ‹ˆλ‹€.


#include <iostream>
#include <vector>
using namespace std;
int N, M, num,result;
vector<int> adj;
int main(void) {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int value;
		cin >> value;
		adj.push_back(value);
	}
	int le = 1;
	int ri = 1000000001;
	while (le <= ri) {
		int mid = (le + ri) / 2;
		long long cnt = 0;
		for (int i = 0; i < M; i++) {
			cnt += (adj[i] / mid);
			if (adj[i] % mid) cnt += 1;
			// λ‚˜λˆ„μ–΄ 떨어지지 μ•ŠμœΌλ©΄ +1
		}
		if (cnt <= N) {
			result = mid;
			ri = mid - 1;
		}
		else le = mid + 1;
	}
	cout << result<< '\n';
	return 0;
}