문제링크
여러모로 배울게 많은 문제였다.
문제의 조건을 읽어보면 K개의 랜선을 적당한 길이로 잘라서 N개의 랜선으로 만들때 최대 랜선의 길이를 구해야 한다. 단순하게 1 ~ MAX(K) 의 길이를 모두 확인해보면 O(MAX(K)^2)
의 시간복잡도로 문제를 해결할 수 있다. 하지만 문제에서 랜선의 최대 길이는 2^31 -1 이기 때문에 시간초과가 발생하게 된다. 따라서 O(N)
정도의 시간복잡도를 갖도록 문제 풀이를 변경해야 한다.
1) K개의 랜선을 저장할 vector
K는 1 x 10^4 개 이하이므로 해당 문제에서 메모리 제한을 걱정할 필요는 없다.
1) K 개의 랜선 길이 오름차순 정렬
O(K*log(K))
2) 1 ~ MAX(K) 범위 탐색O(log2(2^31))
3) 랜선 개수 countO(K)
1 ~ MAX(K) 범위를 이분탐색을 통해 O(log2(2^31))
의 시간복잡도로 자를 랜선의 길이를 선택하고 해당 길이를 통해 몇 개의 랜선을 가질 수 있는지 count 하기 때문에 총 시간 복잡도는 O(log2(2^31)) x O(K)
로 시간내에 해결할 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int k, n;
long long answer;
vector <long long> Lan;
long long count_lan(long long min_value){
int cnt = 0;
for(int i = 0; i < Lan.size(); i++){
long long cut_lan = Lan[i] / min_value;
cnt += cut_lan;
}
return cnt;
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
for(int i = 0; i < k; i++){
int number;
cin >> number;
Lan.push_back(number);
}
sort(Lan.begin(), Lan.end());
long long start = 1, end = Lan[k-1];
while(start <= end){
long long mid = (start + end) / 2;
long long cnt = count_lan(mid);
// n개의 랜선을 만들지 못할 경우, 더 적은 길이로 잘라야 한다.
if(cnt < n) end = mid - 1;
else{
if(mid >= answer)answer = mid;
start = mid + 1;
}
}
cout << answer;
return 0;
}
처음 문제를 읽고 제한시간 내 통과를 위해 이분탐색 풀이를 떠올리는데 까지는 별로 시간이 걸리지 않았다. 하지만 크게 2 가지 실수를 해서 AC 를 받는데 까지 시간이 오래 걸렸다.
1) 가장 짧은 랜선을 사용하지 않을 수도 있다.
처음 문제를 접근할 때 가져온 K개의 랜선중에서 가장 짧은 랜선을 무조건 사용한다고 생각하고, 1 ~ MAX(K) 의 범위가 아닌 1 ~ MIN(K) 의 범위에서 탐색을 진행했다.
3 6
40
20
2
//정답 : 10
그렇게 되면 위와 같은 테스트 케이스를 통과할 수 없게 된다. 따라서 MAX(K) 까지의 모든 case를 탐색해야 한다.
2) long long 자료형을 사용해야 한다.
문제의 조건에 랜선의 길이는 2^31 - 1
이하라고 명시되어 있기 때문에 int 를 사용해서 탐색을 진행할 수 있을거라 생각했다. 하지만 K개의 랜선 중 최대값이 2^31 -1
인 경우,
이분탐색을 진행할 때 int mid = (start + end) / 2;
연산을 진행하기 때문에
start = 1, end = 2^31 -1
이기 때문에 mid는 integer overflow 가 발생하게 된다.
1 1
2147483647
//정답: 2147483647
🔥이분탐색 문제도 많이 풀어봐야겠다!