[BOJ] 백준 1654 랜선 자르기

출처: https://www.acmicpc.net/problem/1654

Approach

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

[탐색] Parametric Search 

[탐색] Parametric Search

0 (left)에서 가지고 있는 가장 긴 랜선 길이(right)까지

모든 경우의 수로 몇 개의 랜선이 나올 수 있는지 구한다면 TLE 발생

 

따라서 left ~ right 기준으로 해서 모두 탐색하지 않고 이분 탐색으로

기준 잡는 횟수를 줄인다.

제출 코드에서는 right는 LLong_MAX로 간단하게 처리

 

주의 사항

- 자른 랜선의 개수가 n개 이상이기에 n개로 맞게 떨어질 필요가 없다.

- int형으로 처리하는 경우 overflow 발생하므로 long long 으로 처리

---

#include <stdio.h>
#include <climits>
typedef long long LL;
int N, K, cnt, lan[10001];
LL left, right, mid, ans;

int main(void) {
    // freopen("input.txt", "r", stdin);
    
    scanf("%d %d", &K, &N);
    for (int i = 0; i < K; i++) {
        scanf("%d", lan + i);
    }
    
    right = LLONG_MAX;
    while (left <= right) {
        cnt = 0; // 랜선 개수
        mid = (left + right) / 2; // 기준
        // 가지고 있는 K개의 랜선을 mid 길이로 자를 때 개수
        for (int i = 0; i < K; i++) {
            cnt += (lan[i] / mid);
        }
        // N개 이상을 만족한다면 기준 길이(mid)를 올린다.
        if (cnt >= N){
            left = mid + 1;
            if (mid > ans)
                ans = mid;
        }
        else
            right = mid - 1;
    }
    printf("%lld\n", ans);
}