[백주 2805번/C언어] 나무 자르기

백준 2805번 문제를 merge sort (합병 정렬)을 이용하여 풀어보았습니다.

 

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

 

 

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

 

 

 

 이 문제는 여러 번의 시간초과를 겪은 끝에 성공했는데, 처음 몇 번 시도가 모두 O(n^2)의 시간복잡도를 가진 코드여서 이를 개선하려는 노력을 많이 했다. 결국 O(NlogN)의 시간복잡도를 가진 merge sort를 활용하여 문제를 해결할 수 있었다.

 

 나무의 개수인 N과 필요한 총 나무의 길이인 M이 터미널 입력으로 주어지면, 자를 수 있는 최대 나무의 높이를 구해서 출력하면 된다. 여기서 자를 수 있는 최대 나무의 높이라는 것은, 해당 높이를 초과하는 길이의 합이 M이상이 되는 최대 높이를 말한다. 예를 들어 길이가 10인 나무가 있고 이를 7의 높이로 자르면 우리는 3만큼의 나무를 가질 수 있다. 이렇게 가지게 되는 모든 길이의 합이 M보다 크거나 같아야 하는 것이다. 

 내가 사용한 방법을 간략히 먼저 언급하면, 우선 입력받은 나무들의 길이를 merge sort를 이용하여 내림차순으로 정렬하고, 그중 최대 길이(즉 첫 번째 요소)부터 시작해서 하나씩 빼가며, M의 길이를 충족할 때까지 순회한다. 

 

 다음으로는 코드에 대해서 설명하겠다.  Merge Sort의 구현은 앞선 포스팅에서 보다 자세히 설명한 것이 있으므로 아래 글을 참고하기 바란다. 함수 swap(), merge(), mergeSort() 모두 merge sort 구현을 위한 함수들이므로, 설명을 생략하겠다.

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

[백준 2751번/C언어] 수 정렬하기, Merge Sort로 풀이

 

 

 다음으로는 main 함수를 살펴보겠다. 나무의 개수인 N과 필요한 나무의 길이인 M을 입력을 받고, 나무 각각의 높이를 저장할 len 배열에 나무 개수만큼의 메모리를 할당해 준다. 그리고 나무 개수만큼 반복하며 나무 각각의 높이를 입력받는다. 만약 나무의 개수가 하나 뿐이라면, 문제에서 언급된 대로 필요한 길이만큼의 나무를 못 구하는 경우는 없으므로, M보다 해당 나무의 높이가 더 클 것이다. 따라서 우리가 출력할 최대 나무 높이는 해당 나무의 길이에서 필요한 나무의 길이를 뺀, 즉 필요 없는 부분의 길이가 된다. 따라서 그냥 입력받은 하나의 나무의 길이에서 필요한 나무의 길이인 M을 빼주면 된다.  나무의 개수가 두 개 이상이라면 이를 정렬(앞서 언급한 merge sort 사용)해준 후 본격적으로 최대 나무 높이 찾기를 시작한다. 변수 i는 현재 순회하고 있는 나무의 index에 해당하기도 하지만, 현재 높이에서 몇 개의 나무가 해당하는지도 함께 나타낸다. 이게 무슨 말이냐면, 만약 4 5 7 10의 길이의 나무들이 있다고 해보자. 이때 우리가 확인하고 있는 높이(결과값)가 8이라면 10 하나만 해당된다. 즉, 해당 높이보다 높아서 잘라낼 수 있는 나무가 10 하나라는 의미이다. 하지만 만약 현재 확인 중인 높이가 5라면 7과 10이 해당(높이가 5인 나무는 잘라낼 수 없으므로 해당되지 않는다)된다. 이를 확인해야 하는 이유는, 높이를 바꿔가면서 확인할 때마다 잘라낼 수 있는 길이의 합을 각각 구하는 과정을 반복하게 되면 O(n^2)의 시간복잡도가 발생하기 때문에, 이렇게 현재 잘라낼 수 있는 나무의 개수만큼만 현재까지 구한 길이의 합에 더해주는 방식을 택했기 때문이다. 그리고 res 변수는 현재 확인하고 있는 높이를 나타내는 변수로, 최종적으로는 최대 높이를 담게 되어 마지막에 이를 출력해 주면 된다. 이렇게 변수를 설정해주고 나면 while문을 통해 M이 0보다 클 때까지, 나무 중 최대 높이부터 시작해서 res 변수로 하나씩 순회하면서 M값을 충족하는지를 확인해준다. 

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

void swap(int **ary, int l, int r) {
    int temp = (*ary)[l];
    (*ary)[l] = (*ary)[r];
    (*ary)[r] = temp;
}

void merge(int **ary, int l, int mid, int r) {
    int *temp = (int *)malloc(sizeof(int) * (r - l + 1));
    if (temp == NULL) return;
    
    int fixedL = l;
    int fixedR = r;
    r = mid;
    int num = 0;
    while (l < mid && r <= fixedR) {
        if ((*ary)[l] > (*ary)[r]) temp[num++] = (*ary)[l++];
        else temp[num++] = (*ary)[r++];
    }
    while (l < mid) temp[num++] = (*ary)[l++];
    while (r <= fixedR) temp[num++] = (*ary)[r++];
    
    num = 0;
    for (int i = fixedL; i <= fixedR; i++) {
        (*ary)[i] = temp[num++]; 
    }
}

void mergeSort(int **ary, int l, int r) {
    if (l >= r) return;
    if ((r - l) == 1) {
        if ((*ary)[l] < (*ary)[r]) swap(ary, l, r);
        return;
    }
    
    int mid = (l + r + 1) / 2;
    mergeSort(ary, l, mid - 1);
    mergeSort(ary, mid, r);
    merge(ary, l, mid, r);
}

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    
    int *len = (int *)malloc(sizeof(int) * N);
    if (len == NULL) return 1;
    for (int i = 0; i < N; i++) scanf("%d", &(len[i]));
    
    if (N == 1) {
        printf("%d", (len[0] - M));
        return 0;
    }
    
    mergeSort(&len, 0, N-1);
        
    int i = 1;
    int res = len[0];
    while (M > 0) {
        while (len[i] == res) i++;
        res--;
        M -= i;
    }
    printf("%d", res);
}