43번 뮤직비디오 질문

Question

안녕하세요 강사님 🙂 43번 뮤직비디오의 채점 폴더의 2번 케이스의 output이 23이 되어야 하는게 아닌지 질문드립니다. 현재 2번 케이스 10 3 6 5 8 5 6 8 7 6 6 7 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; }

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 뮤직비디오 문제에서 제시해 주신 경우를 잘 살펴보았습니다. 문제에서 분배할 수 있는 DVD의 최대 용량을 최소화하려면 이분 탐색을 제대로 수행하여 올바른 값을 찾아야 합니다. 제시해 주신 입력 값에 대한 답변은 다음과 같습니다. 뮤직비디오의 길이를 담은 배열을 정렬한 후, 이분 탐색을 통해 각 DVD에 들어갈 최대 용량을 결정합니다. 여기서 각각의 DVD는 최대 길이가 제한되어 있으므로 제대로 된 분배가 될 수 있도록 탐색해야 합니다. 제시해 주신 입력 값의 경우, DVD의 수가 3개로 제한되어 있고 각 길이가 5, 5, 6, 6, 6, 6, 7, 7, 8, 8 인 상황입니다. 이를 (5, 5, 6, 6), (6, 6, 7), (7, 8, 8)과 같이 나눴을 때, 각 DVD의 합은 22, 19, 23이 됩니다. 여기서 가장 긴 DVD는 길이가 23이므로 이는 가능한 하나의 답입니다. 하지만 문제에서 요구하는 것은 모든 DVD 중 &lsquo;최대 용량을 가진 DVD의 길이를 최소화&rsquo;하는 것이므로 이분 탐색 과정에서 최적의 값을 정확하게 찾아내야 합니다. 이는 각 DVD별 최대 용량이 처음부터 끝까지 동일하게 유지되는 것이 아니라, 각 이분 탐색 스텝에서 해당 범위 안에서 가능한 최소값을 찾기 위해 조절되어야 합니다. 제시하신 코드에서 이분 탐색 과정에 있어서 lt와 rt의 값을 업데이트하는 조건 중 cnt <= M일 때 rt를 mid로 업데이트하는 점이 중요한 요소입니다. 이 조건에 따라 이분 탐색을 반복하며 최적의 해를 찾아가는 과정에서 23이 아닌, 더 낮은 값을 찾을 수 있을 것입니다. 코드의 올바른 실행 여부는 실제로 입력 값을 제공하고 코드를 실행하여 결과를 확인함으로써 검증할 수 있습니다. 혹시 문제가 있다면, 강사님 또는 인프런 커뮤니티를 통해 추가적인 해설이나 도움을 받으실 수 있습니다. 감사합니다.