[C++][BOJ] 2792λ² λ³΄μ μμ(feat. μ΄λΆ νμ)
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;
}