백준) 1654 랜선 자르기

랜선 자르기

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

나무 자르기(http://js1jj2sk3.tistory.com/64?category=749321)와 비슷한 문제다.

K개의 랜선을 적절하게 같은 길이로 잘라 N개의 랜선을 만들어야 하는데,

N개를 만들지 못하는 경우는 없다고 주어졌다.

길이는 모두 정수 값이므로, 나무 자르는 문제와 같이 가능한 모든 길이를 시도해 보면 된다.

마찬가지로 이분 탐색으로 범위를 줄여나갈 수 있고, 현재 시도 중인 길이에 대해 두 가지 케이스가 발생한다.

1. 잘라봐도 N개를 만들지 못할 때

더 긴 길이로 잘라봐야 만들지 못할것이 자명하므로 왼쪽 부분으로 좁혀서 탐색한다.

2. N개를 만들 수 있을 때

더 긴길이를 시도해 봐야 하므로 오른쪽 부분으로 좁혀서 탐색한다.

범위를 좁히다 보면 하한선과 상한선이 엇나가게 될 것이고, 중간에 기록해둔 값들 중 최대 길이가 정답이 된다.

코드로 옮기면 다음과 같다.

#include <stdio.h>
using namespace std;
 
int k, n;
int lan[10000];
 
bool chk(int mid) {
    int cnt = 0;
 
    for (int i = 0; i < k; ++i)
        cnt += lan[i] / mid;
 
    return cnt >= n;
}
 
int main() {
    scanf("%d %d", &k, &n);
 
    int max = 0;
    for (int i = 0; i < k; ++i) {
        scanf("%d", &lan[i]);
        if (max < lan[i])
            max = lan[i];
    }
    
    long long left = 1, right = max;
    int ans = 0;
 
    while (left <= right) {
        long long mid = (left + right) / 2;
 
        if (chk(mid)) {
            if (mid > ans)
                ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    printf("%d", ans);
 
    return 0;
}

left를 초기화 할 때 1이 아닌 0으로 한다면 mid가 0이 되버려 런타임 오류가 발생할 수도 있다.