#1654. 랜선자르기

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

1. 문제 이해

 저 같은 경우는 문제 이해에서 완벽하게 넘어가지 않아 꽤나 고생했던 문제입니다.

함정 point는 n개의 똑같은 랜선을 만들어야 하는데 n보다 큰 경우인 n+1, n+2 경우에도 최대값을 체크해 줘야 한다는 것 입니다.

2. 접근방법

두가지 부분에서 조심해야 합니다.

첫 번째, 시간초과에 주의해야 합니다. 

완전탐색을 할 경우,  시간이 초과하기 때문에 binary search를 사용해야 합니다.

두 번째, 범위초과에 주의해야 합니다.

int 형으로 선언할 경우, 범위가 초과하는 경우(예를 들어, left(2^31-1 / 2)+right(2^31) / 2 = mid(int형 초과), 잘린 갯수(1로 잘랐을대 int형 초과))가 발생할 수 있기 때문에 long long형을 사용하도록 합니다.

세 번째,

저 같은 경우는 속도를 올리기 위해서 

'가장 작은 값을 기준으로 0부터 가장 작은 값 까지 이분탐색을 하자!' 로 접근하였습니다.

하지만 이렇게 접근한 경우, 밑의 test case 에서는 0이 출력 되버립니다. 즉, 완전 탐색이 할 필요가 있다는 것입니다.

4 5

100

200

302

400

그래서 최대값을 찾아 접근하여야 합니다. 최대값으로 설정할경우에도 이분탐색으로 탐색하기 때문에 O(logN) 이 되므로 시간 초과에 대해서 걱정 하지 않아도 됩니다.

3. 문제 해결

#include <cstdio>
#define MAX_SIZE 10005
 
using namespace std;
 
int k, n;
long long res;
int arr[MAX_SIZE];
 
long long calc_lens(long long len) {
    long long output = 0;
    for (int i = 0; i < k; i++) {
        output += (arr[i] / len);
    }
    return output;
}
 
int main() {
    scanf("%d %d", &k, &n);
 
    long long _max = 0;
    for (int i = 0; i < k; i++) {
        scanf("%d", &arr[i]);
        _max = _max < arr[i] ? arr[i] : _max;
    }
 
    long long l = 1, r = _max;
    while (l <= r) {
        long long mid = (l + r) / 2;
        long long tmp = calc_lens(mid);
 
        if (tmp < n) {            // 크게 잘른것, 자르는 크기 줄여주기
            r = mid - 1;
        }
        else {                    // 크거나 같은경우
            res = res < mid ? mid : res;
            l = mid + 1;
        }
    }
 
    printf("%lld\n", res);
    return 0;
}

※ long long 형은 9byte로 int(4byte)보다 더 많은 수를 표현할 수 있다.

※ MAX_SIZE 실수를 자꾸 한다.... 시간 초과가 날 경우 용량을 잘 확인하자!!!