πŸ“ Coding Test Study/Algorithm Problem

[C++][BOJ] 2792번 보석 μƒμž(feat. 이뢄 탐색)

ibelieveinme 2024. 5. 21. 01:09
728x90

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

 

μ•„μ΄λ“€μ˜ μˆ˜μ™€ 보석 μƒ‰μƒμ˜ 수, λ³΄μ„μ˜ κ°œμˆ˜κ°€ μ£Όμ–΄μ§„λ‹€.

λͺ¨λ“  보석을 λ‚˜λˆ„μ–΄μ€„ λ•Œ μ΅œλŒ€ν•œ 차이가 λ‚˜μ§€ μ•Šκ²Œ λ‚˜λˆ„μ–΄μ£ΌλŠ” 방법을 κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€. ν•œ 아이가 κ°–λŠ” λ³΄μ„μ˜ 수λ₯Ό μ§ˆνˆ¬μ‹¬μ΄λΌ ν‘œν˜„ν–ˆλ‹€.

이 λ•Œ ν•œ μ•„μ΄λŠ” 같은 λ³΄μ„μ˜ μƒ‰μƒλ§Œ κ°€μ Έμ•Ό ν•œλ‹€. λ˜ν•œ, 보석을 λͺ»λ°›λŠ” μ•„μ΄λŠ” μžˆμ–΄λ„ λ‚¨λŠ” 보석은 μ—†μ–΄μ•Ό ν•œλ‹€.

 

[μž…λ ₯]

첫째 쀄에 μ•„μ΄λ“€μ˜ 수 Nκ³Ό μƒ‰μƒμ˜ 수 M이 μ£Όμ–΄μ§„λ‹€. (1 ≤ N ≤ 109, 1 ≤ M ≤ 300,000, M ≤ N)

λ‹€μŒ M개 μ€„μ—λŠ” ꡬ간 [1, 10^9]에 ν¬ν•¨λ˜λŠ” μ–‘μ˜ μ •μˆ˜κ°€ ν•˜λ‚˜μ”© μ£Όμ–΄μ§„λ‹€. K번째 쀄에 μ£Όμ–΄μ§€λŠ” μˆ«μžλŠ” K번 색상 λ³΄μ„μ˜ κ°œμˆ˜μ΄λ‹€.

[좜λ ₯]

첫째 쀄에 μ§ˆνˆ¬μ‹¬μ˜ μ΅œμ†Ÿκ°’μ„ 좜λ ₯ν•œλ‹€.

 

 

[풀이]

ν•˜λ‚˜μ˜ λ³΄μ„μ˜ μˆ˜κ°€ μ΅œλŒ€ 10^9 κ°€ μ£Όμ–΄μ§€λ―€λ‘œ λ‹¨μˆœ μ™„μ „νƒμƒ‰μœΌλ‘œλŠ” ν’€ 수 μ—†λ‹€.

μ΄λ ‡κ²Œ 큰 μˆ˜κ°€ μ£Όμ–΄μ§€κ³  μ΅œμ†Œμ˜ 경우λ₯Ό μ°ΎλŠ” κ²½μš°μ— '이뢄탐색' μ•Œκ³ λ¦¬μ¦˜μ„ μ΄μš©ν•œλ‹€.

 

이 λ¬Έμ œμ—μ„œ 이뢄탐색을 μ μš©ν•˜λŠ” 법은 μ§ˆνˆ¬μ‹¬μ΄ κ°€μ§ˆ 수 μžˆλŠ” μ΅œμ†Œ μˆ˜μ™€ μ΅œλŒ€μˆ˜λ₯Ό ν•œμ •ν•˜κ³  쀑간값뢀터 νƒμƒ‰ν•˜λ©° μ΅œμ†Œ μ§ˆνˆ¬μ‹¬μ„ μ°ΎλŠ” 것이닀.

 

예제 1을 봐보자.

5 2
7
4

μ•„μ΄λ“€μ˜ 수: 5, 보석 색깔 2

보석 색깔 1의 개수: 7

보석 색깔 2의 개수: 4

 

이 λ•Œ, μ΅œμ†Œ μ§ˆνˆ¬μ‹¬μ€ 1, μ΅œλŒ€ μ§ˆνˆ¬μ‹¬μ€ 7이라고 생각해볼 수 μžˆλ‹€.

μ΅œλŒ€ μ§ˆνˆ¬μ‹¬μ΄ 7인 μ΄μœ λŠ” ν•œ μ•„μ΄λŠ” λ°˜λ“œμ‹œ 같은 μƒ‰κΉ”μ˜ λ³΄μ„λ§Œ κ°€μ§ˆ 수 μžˆμœΌλ―€λ‘œ ν•œ 아이가 κ°€μ§ˆ 수 μžˆλŠ” μ΅œλŒ€ λ³΄μ„μ˜ κ°œμˆ˜λŠ” 보석 색깔1의 7이기 λ•Œλ¬Έμ΄λ‹€.

 

λ”°λΌμ„œ 1 ~ 7을 μ΄λΆ„νƒμƒ‰ν•˜λ©° μ΅œμ†Œ μ§ˆνˆ¬μ‹¬μ„ μ°ΎλŠ”λ‹€.

(참고둜 이뢄탐색은 쀑간값뢀터 νƒμƒ‰ν•˜κ³  정닡이 쀑간값을 κΈ°μ€€μœΌλ‘œ μ™Όμͺ½μ— μžˆλŠ”μ§€, 였λ₯Έμͺ½μ— μžˆλŠ”μ§€ Up & Down κ²Œμž„μ„ ν•˜λŠ” 것이닀. 1~7의 쀑간값은 '(μ΅œμ†Œκ°’ + μ΅œλŒ€κ°’) / 2' μˆ˜ν•™ κ³΅μ‹μœΌλ‘œ ꡬ할 수 μžˆλ‹€.)

 

1) μ§ˆνˆ¬μ‹¬μ„ 4 라고 κ°€μ •ν•˜κ³  보석을 λ‚˜λˆ λ³΄μž. (1+7) / 2 = 4

3λͺ…μ—κ²Œ λ‚˜λˆ μ€„ 수 μžˆλ‹€. 5λͺ…보닀 μ μœΌλ―€λ‘œ 더 μ„Έμ„Έν•˜κ²Œ μͺΌκ°€ 수 μžˆλ‹€λŠ” 것을 μ•Œ 수 μžˆλ‹€. 더 μž‘μ€ μ§ˆνˆ¬μ‹¬ μ§€μˆ˜λ₯Ό μ°ΎκΈ° μœ„ν•΄ μ΅œλŒ€κ°’μ„ '쀑간값 -1' 둜 κ°±μ‹ ν•˜κ³  λ‹€μ‹œ μ°Ύμ•„λ³΄μž.

 

2) μ΅œμ†Œκ°’ 2, μ΅œλŒ€κ°’ 3 => 쀑간값 2(μ§ˆνˆ¬μ‹¬μ„ 2) 둜 두고 보석을 λ‚˜λˆ λ³΄μž.

5개 μ΄μƒμœΌλ‘œ μͺΌκ°œμ§€λ―€λ‘œ '보석 λ‚˜λˆ„κΈ° > 아이듀 수' κ°€ λ˜λ―€λ‘œ 보석이 λ‚¨μ•„μ„œ μ•ˆλœλ‹€. 더 큰 κ°’μœΌλ‘œ λ‚˜λˆ μ•Ό ν•˜λ―€λ‘œ μ΅œμ†Œκ°’μ„ '쀑간값 +1' 둜 κ°±μ‹ ν•˜κ³  νƒμƒ‰ν•΄λ³΄μž.

 

3) μ΅œμ†Œκ°’ 2, μ΅œλŒ€κ°’ 3 => 쀑간값 2(μ§ˆνˆ¬μ‹¬μ„ 2) 둜 두고 보석을 λ‚˜λˆ λ³΄μž.

2번과 λ™μΌν•œ κ²½μš°μ΄λ―€λ‘œ μ΅œμ†Œκ°’ = 쀑간값 + 1 둜 κ°±μ‹ ν•˜κ³  λ‹€μ‹œ νƒμƒ‰ν•΄λ³΄μž.

 

4) μ΅œμ†Œκ°’ 3, μ΅œλŒ€κ°’ 3 => 쀑간값 3 (μ§ˆνˆ¬μ‹¬ 3)

5λͺ…μ—κ²Œ λ‚˜λˆ μ€„ 수 μžˆλ‹€. λ˜ν•œ 'μ΅œμ†Œκ°’ = μ΅œλŒ€κ°’' μ΄λ―€λ‘œ 더이상 이뢄탐색을 μ§„ν–‰ν•  수 μ—†λ‹€. λ”°λΌμ„œ μ΅œμ†Œ μ§ˆνˆ¬μ‹¬ μ§€μˆ˜λŠ” 3이닀.

 

μ΄λ ‡κ²Œ μ§ˆνˆ¬μ‹¬ 값을 μ€‘κ°„κ°’μœΌλ‘œ 정해두고 Up & Down ν•˜λ©° μ΅œμ†Œ μ§ˆνˆ¬μ‹¬μ„ 찾으면 λœλ‹€. μ‹œκ°„λ³΅μž‘λ„λŠ” O(logN) !

 

 

[μ½”λ“œ]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int childrenNum, colorNum, input;
int minNum = 1, maxNum = 0;
vector<int> colors;

int GetJealousy();

int main() {

	cin >> childrenNum >> colorNum;
	for (int i = 0; i < colorNum; i++) {
		cin >> input;
		colors.push_back(input);
		maxNum = max(maxNum, input);
	}

	cout << GetJealousy() << "\n";

	return 0;
}

int GetJealousy() {
	int jealousy = 0;

	while (minNum <= maxNum) {
		int mid = (minNum + maxNum) / 2;
		int divideNum = 0;

		for (int color : colors) {
			if (color % mid) divideNum += (color / mid) + 1;
			else divideNum += (color / mid);
		}

		if (divideNum <= childrenNum) {
			jealousy = mid;
			maxNum = mid - 1;
		}
		else minNum = mid + 1;
	}
	return jealousy;
}
728x90