[BOJ알고리즘, C++]#2217_로프, 정렬 알고리즘, 병합 정렬

 

#1. 문제

2217번: 로프

 

---

 

#2. 풀이

 

1. 병합 정렬

[알고리즘]#3_정렬 알고리즘

 

[정의] : 병합 정렬 알고리즘은  분할-정복 알고리즘을 기반으로, 주어진 배열을 두 개의 작은 부분 배열로 분할해 각 부분 배열을 재귀적으로 정렬하여, 최종적으로 정렬된 두 부분 배열을 병합해 하나의 정렬된 배열을 얻는 정렬 알고리즘입니다.

* 병합 정렬 vs 퀵 정렬 :  퀵 정렬과 병합 정렬의 가장 큰 차이점은 분할 작업과 정렬 작업의 순서입니다. 병합 정렬은 주어진 배열을 더 이상 나눌 수 없는 충분히 작은 크기(Base Case)까지 분할하고, 두 부분 배열을 병합하며 정렬을 수행하는 반면, 퀵 정렬은 배열의 피벗을 설정해 왼쪽 부분 배열은 피벗보다 작은 원소들, 오른쪽 부분 배열은 피벗보다 큰 원소들로 분할하고, 이를 충분히 작은 크기가 될 때까지 재귀적으로 수행하며 정렬을 수행합니다. 정리하면, 병합 정렬은 우선적으로 Base Case까지 분할 작업을 모두 수행하고, 재귀적으로 병합 과정을 수행하며 정렬하는 반면, 퀵 정렬은 부분적으로 정렬 작업과 분할 작업을 동시에 수행하며, 이는 Base Case가 될 때까지 재귀적으로 수행합니다.

 

2. N개, N-1개, N-2개... 로프가 버틸 수 있는 최대 중량의 최대 값 찾기!

 

1. 먼저, 각 로프가 감당 가능한 최대 중량을 오름차순으로 정렬합니다.
2. 감당 가능한 최대 중량이 가장 낮은 첫 번째 로프는 병렬 연결이 가능한 로프의 개수는 N개이며, 두 번째 로프는 N-1개, 세 번째 로프는 N-2개... 1개입니다.
3. 이를 통해, 병렬연결을 통해 (현재 최대 중량 * N-i)을 버틸 수 있게 됩니다.
4. 따라서, 감당 가능한 최대 중량 값을 차례대로 순회하며 (N-i) 개의 로프와 현재 로프의 버틸 수 있는 최대 중량 값을 곱해 병렬연결을 통해 감당 가능한 최종 중량 값을 구하고, 최대가 되는 중량 값을 출력합니다.

 

---

 

#3. 코드

 

// #1. 병합 정렬

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

int N;
vector<int> weights;

/* [문제] : 최대 중량/개수 = 각 로프에 걸리는 중량, 최대 중량 = 각 로프에 걸리는 최대 중량 * 개수
 * [해결] 
 *        1. 오름차순 정렬
 *        2. 현재 로프가 감당 가능한 최대 중량(현재 로프가 감당 가능한 중량 * 현재 로프 포함 병렬 처리 가능한 로프의 개수)
 *        3. 정렬된 배열을 순서대로 탐색하며, 최대 중량 찾기
*/

void Merge(vector<int>& v, int l, int m, int r)
{
    int leftSize = m - l + 1;
    int rightSize = r - m;
    
    vector<int> leftHalf(leftSize);
    vector<int> rightHalf(rightSize);
    
    for(int i=0; i<leftSize; ++i)
        leftHalf[i] = v[l+i];
    for(int i=0; i<rightSize; ++i)
        rightHalf[i] = v[m+1+i];
    
    int leftIdx = 0;
    int rightIdx = 0;
    int resIdx = l;
    
    while(leftIdx < leftSize && rightIdx < rightSize)
    {
        if(leftHalf[leftIdx] <= rightHalf[rightIdx])
        {
            v[resIdx++] = leftHalf[leftIdx++];
        }
        else
        {
            v[resIdx++] = rightHalf[rightIdx++];
        }
    }
    
    while(leftIdx < leftSize)
        v[resIdx++] = leftHalf[leftIdx++];
    
    while(rightIdx < rightSize)
        v[resIdx++] = rightHalf[rightIdx++];
    
}
    
void MergeSort(vector<int>& v, int l, int r)
{
    if(l < r)
    {
        int m = l + (r-l)/2;
        
        MergeSort(v, l, m);
        MergeSort(v, m+1, r);
        
        Merge(v, l, m, r);
    }
}
    
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    
    weights.resize(N);
    
    for(int i=0; i<(int)weights.size(); ++i)
        cin >> weights[i];
    
    // #1. 병합 정렬(오름차순 정렬)
    MergeSort(weights, 0, N-1);
    
    // #2. 최대 중량 = 각 로프에 걸리는 최대 중량 * 병렬 연결된 로프의 개수
    int res = INT_MIN;
    for(int i=0; i<(int)weights.size(); ++i)
    {
        res = max(res, weights[i]*((int)weights.size()-i));
    }
    
    cout << res;
    
    return 0;
}

 

---