BOJ 1654번: 랜선 자르기

문제 설명

가지고 있는 랜선의 개수 K, 필요한 랜선의 개수 N이 입력될 때 랜선 최대 길이 구하기

🔗 문제 링크

핵심 아이디어

• 길이 X로 잘랐을 때 N개 이상의 랜선을 만들 수 있는지 판단하는 함수를 만들기
• 이분 탐색을 통해 만들 수 있는 랜선 길이 중 가장 긴 길이를 찾기
  • mid 길이로 만들 수 있으면 더 긴 길이도 시도해본다 (st = mid)
  • 만들 수 없으면 mid보다 짧은 길이만 고려한다 (en = mid - 1)

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int k, n;
int arr[10005];

bool solve(ll x){
    ll cur = 0;
    for(int i = 0; i < k; i++) cur += arr[i] / x;
    return cur >= n;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> k >> n;
    for(int i = 0; i < k; i++) cin >> arr[i];
    
    ll st = 1;
    ll en = 0x7fffffff; // 2^31 - 1
    
    while(st < en){
        ll mid = (st + en + 1)/2;
        if(solve(mid)) st = mid;
        else en = mid-1;
    }
    
    cout << st;
    
}

16진수 만들기

• f: 1111
• 7: 0111
• 0x7fffffff: 2^31 - 1

‼️ 주의할 점

• ✅ (st + en + 1)/2는 mid = st를 방지하고 위쪽 구간을 우선 탐색하기 위해 필요!
• ❗ 안 그러면 st와 en 사이가 1 차이일 때 mid = st가 계속 유지되며 while(st < en)을 빠져나오지 못할 수 있음