[백준 1654번/C언어] 랜선 자르기, 이진탐색으로 풀이

백준 1654번 문제를 이진탐색(Binary Search)으로 풀어보았습니다. 

백준 1654번: https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

 

문제 내용은 아래와 같습니다. 

 

 

 

 이 문제는 작동하게만 하려는 목표라면 굳이 이진탐색을 사용하지 않아도 되지만, 이진탐색을 사용하지 않으면 시간초과가 발생하기 때문에 효율을 위해서 이진탐색을 써야 하는 문제입니다. 사실 이진탐색만 알면 나머지 구조 자체는 크게 어려울 것이 없는데요, 다만 오버플로우를 처리하는 것에 주의를 해야 합니다. 문제에서는 N과 K, 그리고 랜선 길이까지 int 범위를 벗어나는 변수가 없는 것처럼 보이지만, 그 값들을 더하고 빼가며 답을 찾아야 하기 때문에 오버플로우에 주의해야 합니다. 이진탐색에 대한 간단한 설명은 아래 제 글에서 참고하실 수 있습니다. 다만 해당 글은 해당 문제에 초점이 맞춰져 있기 때문에 보다 자세한 이진탐색에 대한 내용을 알고 싶으시면 다른 글도 참고해 보시는 것을 추천합니다.

https://programming-diary-ina.tistory.com/17

[백준 1920번/C언어] 수 찾기, 이진탐색으로 풀이

 

 

 그럼 제가 문제에 접근한 전반적인 구조를 먼저 설명하겠습니다. 우선 효율성을 위해서 초기에 결과를 탐색할 구간부터 줄이고 싶었는데요, 그래서 결과가 될 수 있는 최대값이 무엇 일지에 대해 먼저 생각해 보았습니다. 그 결과, 아무리 커져도 모든 랜선의 길이를 더하여 N으로 나눈 값보다는 커질 수 없다는 것을 알게 되었습니다. 그래서 초기에 탐색할 구간을 0에서 (모든 랜선의 길이를 더한 값 / N)으로 정하였습니다. (작성하면서 생각해 보니,  K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다는 문제의 가정 때문에 1부터로 구간을 설정해도 되겠다는 생각이 드네요.) 해당 구간 내에서 이진탐색을 통해 결괏값을 찾아내었습니다. 

 이진탐색을 하는 과정에서는 재귀함수를 사용합니다. 우선 중앙값을 찾은 다음 해당 중앙값으로 랜선 길이를 설정했을 때 N개 이상의 랜선을 만들 수 있는지를 체크하고 만약에 만들 수 있고, 중앙값+1 값은 만들 수 없다면, 현재 중앙값이 랜선의 최대 길이라는 뜻이므로 현재 중앙값을 리턴해줍니다. 그리고 현재 중앙값도 만들 수 있고 중앙값+1 값도 만들 수 있다면 현재 중앙값이 조건을 충족하긴 하지만 최대값은 아니라는 뜻이므로 구간을 중앙값+1부터 현재 구간의 최댓값으로 재설정하여 함수를 재수행해줍니다. 마지막으로 현재 중앙값이 N개의 랜선을 만들 수 없다면, 랜선의 길이가 더 작아야 한다는 뜻이므로 구간을 현재 구간의 최솟값부터 현재 중앙값 - 1 값까지로 설정하여 함수를 재수행해줍니다. 이 과정을 계속 반복하여 결괏값을 찾게 됩니다. 

 

 

 구조를 바탕으로 코드를 보다 자세히 살펴보면, 총 3개의 함수로 구성했습니다. 우선 count() 함수는 현재 중앙값으로 얼마나 많은 랜선을 만들 수 있는지 센 후, n개 이상을 만들 수 있으면 1을 아니면 0을 리턴하는 함수입니다. 이 함수를 통해서 현재 중앙값이 조건을 충족하는지 여부를 파악할 수 있습니다. 

 findResult() 함수는 이진탐색을 수행하는 재귀함수입니다. 중앙값을 설정하고, 해당 중앙값이 n개 이상의 랜선을 만들 수 있는지에 따라, 구간을 새롭게 설정합니다. 해당 중앙값이 n개 이상 랜선을 만들 수 없다면, 길이를 줄여 랜선이 더 잘게 쪼개지게 만들어야 한다는 뜻이므로, 더 작은 왼쪽 구간으로 가고, 아니면 오른쪽 구간으로 갑니다. 만약 중앙값이 조건을 충족하는데 중앙값+1이 조건을 충족할 수 없다면 현재 중앙값이 조건을 충족하는 최대값이라는 뜻이므로 이를 그냥 리턴해주면 됩니다. 그리고 함수 가장 첫 부분 조건에서 end가 1이라는 것은 조건을 충족하는 최댓값이 이미 1이라는 것이 확정된 것이므로 1을 리턴해줍니다. 그리고 start가 end보다 크거나 같다는 것은 더 이상 탐색을 수행할 구간이 없다는 뜻이므로 end를 리턴해줍니다. 여기서 start가 아닌 end를 리턴해주는 이유가 있습니다. 문제 조건에 따라서 우리가 받는 경우 중 답이 없는 경우는 없습니다. 따라서 아래 if else문에서 else에 해당하는 재귀에서 start가 end보다 크거나 같아지는 일은 없다는 뜻입니다. (왼쪽 구간으로 진입했다는 것은 아직 랜선을 n개 이상 만들 수 있는 값을 찾지 못했다는 뜻인데, 이렇게 함수에 진입하고 더 이상 탐색할 구간이 없다는 결과가 나온다면 그 말은 답이 없다는 뜻이기 때문입니다.) 결국 해당 if 문에 걸린다는 것은 오른쪽 구간으로부터 진입했다는 뜻인데, 만약 start가 end보다 크다면 start는 구간 내 값이 아니라는 뜻이 되므로 end를 리턴해줘야 합니다. (진입 시 start가 mid+1로 조정된 값이고, end는 이전 end를 그대로 가져온 것이므로 구간 내의 값임을 확신할 수 있기 때문입니다.)

 마지막으로 main 함수에서 k와 n을 입력받고, 초기 랜선의 길이를 저장할 length 배열의 크기를 k로 정의해준 다음 malloc 체크를 해줍니다. 그 이후 length 배열에 초기 랜선 길이를 입력받으면서 res 변수에 총합을 구해줍니다. 이후 k가 1이면 해당 랜선 하나로 n개의 랜선을 만들어야 한다는 뜻이므로 res값은 res에서 n을 나눈 값이 될 것이고, 아니라면 앞서 만들었던 findRes() 함수를 실행시켜 결과를 찾아주면 됩니다. 초기 구간은 0부터 res/n까지로 설정해 줍니다. 마지막으로 결과가 저장된 res값을 출력해 주면 끝납니다. 

#include <stdio.h>
#include <stdlib.h>

int count(int k, long long int res, int n, int *length) {
    long long int count = 0;
    for (int i = 0; i < k; i++) {
        count += (length[i] / res);
        if (count >= n) return 1;
    }
    if (count >= n) return 1;
    return 0;
}

long long int findResult(long long int start, long long int end, int n, int k, int *length) {
    if (end == 1)
        return 1;
    if (start >= end)
        return end;
    
    long long int mid = (start + end + 1) / 2;
    if (count(k, mid, n, length)) {
        if (!count(k, mid+1, n, length))
            return mid;
        else
            return findResult(mid+1, end, n, k, length);
    } else {
        return findResult(start, mid-1, n, k, length);
    }
}

int main() {
    int k, n;
    scanf("%d %d", &k, &n);
    
    int *length = (int *)malloc(sizeof(int) * k);
    if (length == NULL)
        return (1);
    
    long long int res = 0;
    for (int i = 0; i < k; i++) {
        scanf("%d", &(length[i]));
        res += length[i];
    }
    
    if (k == 1)
        res /= n;
    else
        res = findResult(0, (res / n), n, k, length);
    
    printf("%lld", res);
}

 

 앞서 언급한대로 overflow에 주의하여 함수를 구성해야 하는데요, 우선 res변수에는 length 배열 내 값들의 총합이 들어갈 것이기 때문에 long long int로 정의해 줍니다. length 배열에 들어갈 수 있는 최댓값이 2^31-1이므로, 최댓값 두 개만 더해진다고 생각해도 이미 오버플로우가 발생하기 때문입니다. 두 번째로 start와 end에는 long long int로 정의된 res값이 들어갈 수 있으므로 이 역시 long long int로 정의해 주고, res값을 찾을 findResult 함수의 리턴 타입으로 long long int로 설정해 줍니다. mid값 역시 res를 조정하여 설정되는 변수이므로 long long int로 설정해 줍니다. 이런 식으로 overflow 가능성을 체크하는 것을 주의해야 하는 문제입니다.