백준 1654 랜선 자르기 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/1654

아이디어

• 랜선의 길이를 정한다음, K개의 랜선에 각각 나눠보면서 N개 이상이 되는 최대의 개수를 구하면됨
  • 정답이 되는 랜선의 길이를 가지고 이진 탐색 수행
    • 구하려는 랜선길이 이분탐색
    • 이분탐색할때 K개에 대해서 나눠줌
    • N개 이상이 되는 최대 길이를 구함 > upper bound

시간복잡도 계산

• 구하려는 랜선길이 이분탐색 : lg(2^31)
  • 이분탐색할때 K개에 대해서 나눠줌 : O(K)
  • O(lg(2^31) * K) = 31 * 1e4 = 3e5

인트 계산

• 이미 가지고 있는 랜선길이 : 1~2^31 = int 가능
• 자를수 있는 갯수 계산할때 :
  • 제일 작은 1로 자른다고 쳤을때
  • 최대값 : 2^31 * K >> long long 사용

코드

#include <iostream>
#include <algorithm>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
int K,N;
int nums[10010];
 
//
ll cal(int mid) {
    ll rs=0;
    for(int i=0; i<K; i++) rs+=nums[i]/mid;
    
    return rs;
}
int binsearch(ll st, int en, int tar) {
    if(st==en) {
        return st;
    }
    
    int mid = (st+en+1)/2;
    if(cal(mid) >= tar) {
        return binsearch(mid, en, tar);
    }
    else return binsearch(st, mid-1, tar);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> K >> N;
    for(int i=0; i<K; i++) cin >> nums[i];
    
    cout << binsearch(1,pow(2,31)-1, N) << '\n';
}
 

문제유형

• 이분탐새 - 케이스를 이분탐색

비슷한 문제

• https://www.acmicpc.net/problem/1300
• https://www.acmicpc.net/problem/1939
• https://www.acmicpc.net/problem/2805