43번 뮤직비디오 질문

안녕하세요 강사님 🙂

43번 뮤직비디오의 채점 폴더의 2번 케이스의 output이 23이 되어야 하는게 아닌지 질문드립니다.

현재 2번 케이스

<input>

10 3

6 5 8 5 6 8 7 6 6 7

<output>

24

배열 정렬, 5 5 6 6 6 6 7 7 8 8

(5, 5, 6, 6) (6, 6, 7) (7, 8, 8)

(5, 5, 6, 6) = 22

(6, 6, 7) = 19

(7, 8, 8) = 23

24가 아닌 23이 최소 비용이 되는 값이 아닌지 질문드립니다

제가 작성한 코드

void swap(int* a, int* b) {

int temp = *a;

a = b;

*b = temp;

}

int partition(int arr[], int low, int high) {

int pivot = arr[high];

int i = low - 1;

for (int j = low; j < high; j++) {

if (arr[j] < pivot) {

i++;

swap(&arr[i], &arr[j]);

}

}

swap(&arr[i + 1], &arr[high]);

return i + 1;

}

void quickSort(int arr[], int low, int high) {

if (low < high) {

int pivotIndex = partition(arr, low, high);

quickSort(arr, low, pivotIndex - 1);

quickSort(arr, pivotIndex + 1, high);

}

}

int main() {

int N, M;

scanf_s("%d%d", &N, &M);

int* pN = (int*)malloc(sizeof(int) * N);

for (int i = 0; i < N; i++) {

scanf_s("%d", &pN[i]);

}

// 배열 정렬

quickSort(pN, 0, N - 1);

int lt = 1, rt = 0;

// 배열의 모든 요소를 더하여 rt 초기화

for (int i = 0; i < N; i++) {

rt += pN[i];

}

while (true) {

int cnt = 0, sum = 0;

int mid = (lt + rt) / 2;

if (mid == lt)

{

printf("%d", rt);

break;

}

if (mid == rt)

{

printf("%d", rt);

break;

}

 

// 누적 합이 mid를 넘으면 카운트 증가

for (int i = 0; i < N; i++)

{

if ((sum + pN[i]) > mid)

{

sum = 0;

cnt++;

}

// 마지막 배열의 경우 카운트 증가

if (i == N - 1)

cnt++;

sum += pN[i];

}

// 카운트에 따라 이분 탐색 범위 조절

if (cnt <= M) {

rt = mid;

}

else {

lt = mid;

}

mid = (lt + rt) / 2;

}

// 동적 할당한 배열 메모리 해제

free(pN);

return 0;

}

break;

}

if (mid == rt)

{

printf("%d", rt);

break;

}

 

// 누적 합이 mid를 넘으면 카운트 증가

for (int i = 0; i < N; i++)

{

if ((sum + pN[i]) > mid)

{

sum = 0;

cnt++;

}

if (i == N - 1)

cnt++;

sum += pN[i];

}

// 카운트에 따라 이분 탐색 범위 조절

if (cnt <= M) {

rt = mid;

}

else {

lt = mid;

}

mid = (lt + rt) / 2;

}

// 동적 할당한 배열 메모리 해제

free(pN);

return 0;

}