[백준/c++] 1654번: 랜선 자르기
🌱 문제
🌱 풀이
- 이 문제를 처음 읽고
이분 탐색
문제구나! 라는 생각이 바로 들지 않았다... (힌트를 읽고 알았다.ㅠㅠ) - 랜선의 길이가 될 수 있는것은 1부터 ~ 입력받은 랜선 길이의 최댓값이므로, 이를 각각 start, end로 지정하고 이분탐색으로 풀었다.
- 랜선의 길이는 2^31-1 보다 작거나 같은 자연수 라고 하였다.
- 2^31 = 2,147,483,648이다.
ex) mid= (start+end)/2 인데 예를 들어 start=2, end=2,147,648 인경우 mid가 int범위를 넘어가게 되므로 long long으로 선언해 주었다.
🌱 코드
//1654번: 랜선 자르기
/*
이미 있는 랜선 K개 :
1<=k<=10,000
필요한 랜선 N개:
1 <= N <= 1,000,000
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,k;
vector<int> v;
long long answer;
void func(){
// 랜선 길이의 최댓값은 v의 최댓값
long long start=1;
long long end=v[k-1];
//여기 주의 . start==end==mid일때 mid가 최댓값으로 답일수도 있음.
while(start<=end){
long long mid=(start+end)/2;
long long sum=0;
//mid가 현재 자르려는 길이
for(int i=0; i<k; i++){
sum+=v[i]/mid;
}
if(sum>=n){
if(answer<mid)
answer=mid;
start=mid+1;
}else{
end=mid-1;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>k>>n;
for(int i=0; i<k; i++){
int x;
cin>>x;
v.push_back(x);
}
sort(v.begin(), v.end());
func();
cout<<answer<<"\n";
}
Author And Source
이 문제에 관하여([백준/c++] 1654번: 랜선 자르기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@somyeong0623/백준c-1654번-랜선-자르기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)