λ¬Έμ
2792λ²: 보μ μμ
보μ 곡μ₯μμ 보μ μμλ₯Ό μ μΉμμ κΈ°μ¦νλ€. κ°κ°μ 보μμ Mκ°μ§ μλ‘ λ€λ₯Έ μμ μ€ ν μμμ΄λ€. μμ₯ μ μλμ λͺ¨λ 보μμ Nλͺ μ νμλ€μκ² λλμ΄ μ£Όλ €κ³ νλ€. μ΄λ, 보μμ λ°μ§ λͺ»ν
www.acmicpc.net
μ½λ
#include <iostream>
#include <vector>
#define ll unsigned long long int
using namespace std;
int N, M;
vector<ll> v;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>N>>M;
ll max_find = 0;
for(int i=0; i<M; i++){
int inp; cin>>inp;
v.push_back(inp);
max_find += inp;
}
ll start = 1, end = max_find;
ll ans = 0;
while(start <= end){
ll mid = (start + end) / 2;
ll jeal = mid; // μ΅λ μ§ν¬μ¬
ll peo = 0;
for(int i=0; i<M; i++){
if(jeal >= v[i]) peo += 1;
else{
if(v[i] % jeal == 0) peo += v[i] / jeal;
else peo += (v[i] / jeal) + 1;
}
}
if(peo > N) start = mid +1;
else{
ans = mid;
end = mid -1;
}
}
cout<<ans;
}
νμ΄
[λ°±μ€,c++] 6236λ² - μ©λ κ΄λ¦¬
λ¬Έμ 6236λ²: μ©λ κ΄λ¦¬ νμ°λ μ©λμ ν¨μ¨μ μΌλ‘ νμ©νκΈ° μν΄ κ³νμ μ§κΈ°λ‘ νμλ€. νμ°λ μμΌλ‘ NμΌ λμ μμ μ΄ μ¬μ©ν κΈμ‘μ κ³μ°νμκ³ , λμ νν μ°μ§ μκΈ° μν΄ μ νν Mλ²λ§ ν΅μ₯
dkswnkk.tistory.com
μ λ¬Έμ μ κ±°μ μ μ¬ν©λλ€.
μ΅λ μ§ν¬μ¬μ μ λ°νλ κ°μλ₯Ό μ΄λΆ νμμ ν΅ν΄μ μ ν νμ ν΄λΉ μ§ν¬μ¬μ κ°μ§κ³ λͺ¨λ 보μμ νμν©λλ€.
ν΄λΉ 보μμ κ°―μκ° μ§ν¬μ¬μ μ λ°νλ κ°μλ³΄λ€ μλ€λ©΄ κ·Έλ₯ μ λΆ λλ μ€λλ€.
λ§μ½ 보μμ κ°―μκ° μ§ν¬μ¬μ μ λ°νλ κ°μλ³΄λ€ ν΄ λ
- (보μ % μ§ν¬μ¬) == 0 μ΄λΌλ©΄ μ λΆ μ§ν¬μ¬ κ°μλ§νΌ λλ μ€ μ μμΌλ λλ μ£Όκ³ ,
- (보μ % μ§ν¬μ¬) != 0μ΄λΌλ©΄ ν λͺ μ μ§ν¬μ¬λ³΄λ€ μ μ κ°μλ₯Ό λ°κ² λ ν λ μΈμμ μλ₯Ό μΆκ°λ‘ +1 ν΄μ€λλ€.
μ΅μ’ μ μΌλ‘ 보μμ λλ μ€ μΈμμ μ > NμΌ κ²½μ°μ μ§ν¬μ¬μ μ λ°νλ μλ₯Ό λ ν¬κ² μΈν νμ¬ νμνκ³ λ°λμ κ²½μ°μλ λ μκ² μΈν νμ¬ νμν©λλ€.
μμ μ μΆλ ₯ 2λ₯Ό μλ₯Ό λ€μ΄ μ΄ν΄λ³΄λ©΄ λ€μκ³Ό κ°μ΅λλ€.
7 5
7
1
7
4
4
1 4 4 7 7 λ§νΌμ 보μ κ°―μκ° μκ³ , μ§ν¬μ¬μ μ λ°νλ κ°μκ° 4λΌλ©΄ μλμ κ°μ΄ λλ μ€ μ μμ΅λλ€.
κ° λ³΄μμ κ°―μ | 1 | 4 | 4 | 7 | 7 |
λλ μ€ λ³΄μμ κ°―μ | 1 | 4 | 4 | 4, 3 | 4, 3 |
'Algorithm π§π»βπ» > λ°±μ€(BOJ)' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[λ°±μ€,c++] 19939λ² - λ° ν°λ¨λ¦¬κΈ° (0) | 2022.09.14 |
---|---|
[λ°±μ€,c++] 2141λ² - μ°μ²΄κ΅ (0) | 2022.09.13 |
[λ°±μ€,c++] 14627λ² - νλνλ (0) | 2022.09.13 |
[λ°±μ€,c++] 6236λ² - μ©λ κ΄λ¦¬ (0) | 2022.09.08 |
[λ°±μ€,c++] 20040λ² - μ¬μ΄ν΄ κ²μ (0) | 2022.09.07 |
[λ°±μ€,c++] 11561λ² - μ§κ²λ€λ¦¬ (0) | 2022.09.07 |
λκΈ