[BOJ]11582 - 치킨 TOP N (C++)

문제

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

코드

#include <iostream>
#include <vector> 
#include <algorithm>

using namespace std;

int sorted[1048576];
int N;
int stu;
int array[1048576];

void merge(int a[], int m, int middle, int n){
    if((n-m)>(N/stu)) return;
    int i = m; 
    int j = middle + 1;
    int k = m;

    while (i<=middle & j<=n){
        if(a[i]<=a[j]){
            sorted[k++] = a[i++];
        }
        else{
            sorted[k++]=a[j++];
        }
    }

    while(i<=middle) sorted[k++] = a[i++];
    while(j<=n) sorted[k++] = a[j++];
    for(int i=m; i<=n; i++) a[i] = sorted[i];

}

void mergeSort(int a[], int m, int n){
    if(m<n){
        int middle = (m+n)/2;
        mergeSort(a, m, middle);
        mergeSort(a, middle+1, n);
        merge(a, m, middle, n);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N;
    for(int i=0; i< N; i++){
        cin >> array[i];
    }
    cin >> stu; 
    mergeSort(array,0, N-1);

    for(int i=0 ;i<N;i++){
        cout << array[i] << ' ';
    }
}

풀이

이 문제는 merge sort를 사용하는 문제이다.
나동빈님의 merge sort영상을 참고하여 코드를 짰다.
정렬을 하는 코드는 짤 수 있었지만 중간에 어떻게 멈추면 좋을지 오랜 시간 고민했다. 치킨집의 갯수와 학생의 수 모두 2의 거듭제곱이기 때문에 이 조건을 사용하면 좋겠다는 생각이 들었다.
배열의 양 끝 index의 차가 전체 원소 갯수를 학생의 수만큼 나눈 것 보다 크다면 바로 return하여 그 때의 배열의 상태를 출력한다.