인프런 커뮤니티 질문&답변
작성한 질문수
43번 뮤직비디오 질문
작성
·
208
·
수정됨
0
안녕하세요 강사님 🙂
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;
}답변 1
0
안녕하세요, 인프런 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 중 ‘최대 용량을 가진 DVD의 길이를 최소화’하는 것이므로 이분 탐색 과정에서 최적의 값을 정확하게 찾아내야 합니다. 이는 각 DVD별 최대 용량이 처음부터 끝까지 동일하게 유지되는 것이 아니라, 각 이분 탐색 스텝에서 해당 범위 안에서 가능한 최소값을 찾기 위해 조절되어야 합니다.
제시하신 코드에서 이분 탐색 과정에 있어서 lt와 rt의 값을 업데이트하는 조건 중 cnt <= M일 때 rt를 mid로 업데이트하는 점이 중요한 요소입니다. 이 조건에 따라 이분 탐색을 반복하며 최적의 해를 찾아가는 과정에서 23이 아닌, 더 낮은 값을 찾을 수 있을 것입니다.
코드의 올바른 실행 여부는 실제로 입력 값을 제공하고 코드를 실행하여 결과를 확인함으로써 검증할 수 있습니다. 혹시 문제가 있다면, 강사님 또는 인프런 커뮤니티를 통해 추가적인 해설이나 도움을 받으실 수 있습니다.
감사합니다.
문제에 정렬해라는 말이 없는데 정렬을 한 뒤 계산을 하고 있었군요.. ☹ 해당 부분 확인했습니다