Intuition

가능한 capacity를 이진탐색을 통해 후보를 정한 다음, 그때그때 그것이 가능한지 체크한다.
이때, 점점 capacity가 작아지도록 이진탐색하여 최솟값을 찾는다.

Approach

어떤 시점 x부터는 capacity가 모두 가능해진다. 이 x를 찾기 위해 이진탐색을 진행할 것이다.

위의 표에서는 편의를 위해 최댓값을 $2^{31}$로 썼지만, 실제로 이 문제에서의 최댓값은 계산이 가능하다. 문제의 조건에 따라, 최대의 무게로 최대한의 weight length만큼을 1일만에 옮기기 위한 capacity 즉, $500*(5*10^4)=25*10^6$이다.

이진탐색을 진행하며, capacity후보가 days안에 수송이 가능한지 체크하고 가능한 경우 최댓값 변수를 중앙값-1로 업데이트하여 더 작은 capacity후보를 찾도록 설계한다.

int shipWithinDays(int* weights, int weightsSize, int days) {
    int m=1;
    int M=25000000;
    int ans;

    while (m<=M){
        int med=m+(M-m)/2;

        if (possible(med,weights,weightsSize,days)){
            ans=med;
            M=med-1;
        }
        else m=med+1;
    }    

    return ans;
}

 
이제 capacity후보가 days안에 수송이 가능한지 체크를 하는 함수를 작성해야한다.
기본적으로, weights[i]가 capacity보다 크면 해당 capacity는 불가능하다.

int possible(int med, int* weights, int weightsSize, int days){
    ...

    for (int i=0;i<weightsSize;i++){
        if (weights[i]>med) return 0;

        ...
    }
	...
}

 
weights[i]를 누적하다가 capacity를 초과하는 경우, day를 하루 증가시키고 오늘 옮기지 못한 weights[i]는 남겨둔다.
for문이 끝났을 때, 내일 옮겨야 할 weights[i]가 항상 남아있게 되므로 day는 0이 아니라 1로 초기화시킨다.

int possible(int med, int* weights, int weightsSize, int days){
    int cnt=0;
    int day=1;

    for (int i=0;i<weightsSize;i++){
        if (weights[i]>med) return 0;

        cnt+=weights[i];
        if (cnt>med){
            day++;
            cnt=weights[i]; // 내일 옮길 weights[i]
        }
    }

    return days>=day;
}

Solution

int possible(int med, int* weights, int weightsSize, int days){
    int cnt=0;
    int day=1;

    for (int i=0;i<weightsSize;i++){
        if (weights[i]>med) return 0;

        cnt+=weights[i];
        if (cnt>med){
            day++;
            cnt=weights[i];
        }
    }

    return days>=day;
}

int shipWithinDays(int* weights, int weightsSize, int days) {
    int m=1;
    int M=25000000;
    int ans;

    while (m<=M){
        int med=m+(M-m)/2;

        if (possible(med,weights,weightsSize,days)){
            ans=med;
            M=med-1;
        }
        else m=med+1;
    }    

    return ans;
}

Time Complexity

상수로 표현하면,

capacity후보를 이진탐색하는데에 capacity의 최댓값에 log를 취한 $log(25*10^6)$,
해당 capacity가 가능한지 확인하는데에 weights.length인 $5*10^4$ 이다.

rough하게 $O(N logN)$이라 표현할 수 있다.