728x90
문제 1654번
https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
'최대' 이런 단어가 있는 거 보니 이분 탐색으로 풀면 될 것 같다. 입력된 길이 중에서 가장 긴 길이를 maxx에 넣어준다. 그리고 start는 1, end는 가장 긴 길이로 초기화해준다. while문을 이용해 start<=end일 동안 반복해준다. 벡터에 넣어둔 랜선의 길이들을 mid값으로 나눈 후 그 값들을 다 더해서 K가 되는지 확인한다. K개보다 많이 만들어도 K개 만드는 것에 포함되기 때문에 합한 sum값이 K보다 작으면 end를 1감소시켜주고, 아니면 해당 mid값을 result에 넣고 start를 1증가시켜준다.
#include <iostream>
#include <vector>
using namespace std;
long long K, N;
vector <int> v;
int main() {
cin >> N >> K;
long long maxx = 0;
int a;
for (int i = 0; i < N; i++) {
cin >> a;
v.push_back(a);
if (maxx < a) {
maxx = a;
}
}
long long result;
long long start = 1, end = maxx;
while (start <= end) {
long long mid = (start + end) / 2;
int sum = 0;
for (int i = 0; i < N; i++) {
sum += v[i] / mid;
}
if (sum < K) {
end = mid - 1;
} else {
result = mid;
start = mid + 1;
}
}
cout<<result;
return 0;
}
728x90
'백준 > C++' 카테고리의 다른 글
[C++] 백준 2467번 - 용액 (0) | 2024.04.19 |
---|---|
[C++] 백준 2110번 - 공유기 설치 (0) | 2024.04.18 |
[C++] 백준 7795번 - 먹을 것인가 먹힐 것인가 (0) | 2024.04.16 |
[C++] 백준 1225번 - 이상한 곱셈 (0) | 2024.04.15 |
[C++] 백준 1264번 - 모음의 개수 (0) | 2024.04.14 |