[1654] 랜선 자르기

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

이분 탐색을 재귀로 구현해보았습니다!

여기서 중요한 것은 mid와 left right를 롱롱형으로 처리한다는 점입니다.

right 초기값을 signed int의 최대값으로 설정했기 때문에 1 + right를 할 경우에

int범위를 벗어나게 됩니다. 그러므로 롱롱형으로 처리를 했습니다.

이 문제도 마찬가지로 무엇을 이분탐색으로 탐색할 것인가??에 대해서 고민하면 쉽게 풀 수 있습니다.

여기서 탐색할 것은 랜선의 길이입니다. 각 랜선에서 몇미터짜리의 랜선으로 자를 것인가!
처음에 최대값부터 시작해서... 이분탐색을 합니다!

임의의 값으로 랜선을 잘랐을 때 랜선의 수가 요구하는 개수보다 많아지면 더 길게!

반대의 경우는 짧게 탐색을 합니다.

조심해야할 점은 문제에서 최대 길이를 요구했으므로

어떤 길이로 잘랐을때 랜선의 개수 N을 만족하더라도 더 긴 길이의 랜선으로 만들어보아야합니다.

예를들어 200으로 잘랐는데도 랜선 N개를 만족할 수도 있고 201도 만족한다면 답은 201이 되어야한다는 말입니다.

#include <cstdio>
#define MAX_SIZE 10000
#define INF 0x7fffffff
#define ll long long
int data[MAX_SIZE];
int k, n;
int ret;
 
int binary_search(int key, ll left, ll right)
{
    if(left > right) return -1;
 
    ll mid = (left + right) / 2;
 
    int cnt = 0;
    for(int i = 0; i < k; i++) cnt += data[i] / mid;
 
 
    if(cnt >= key)
    {
        ret = mid > ret ? mid : ret;
        return binary_search(key, mid + 1, right);
    }
    else if(cnt < key) return binary_search(key, left, mid - 1);
 
}
 
int main()
{
 
    scanf("%d %d", &k, &n);
 
    for(int i = 0; i < k; i++) scanf("%d", data + i);
 
    binary_search(n, 1, INF);
 
    printf("%d", ret);
 
    return 0;
}