우리는 배열 형태로 연속된 상자에 들어 있는 초콜릿의 수와 이 초콜릿이 배포될 학생 수를 나타내는 숫자 k가 제공됩니다. 여기서 과제는 상자에 들어 있는 초콜릿의 합이 k 학생에게 균등하게 분배될 수 있도록 연속적인 상자를 선택하는 것입니다. 또한 초콜릿의 수가 최대인지 확인해야 합니다.
이를 위해 배열을 왼쪽에서 오른쪽으로 탐색하고 초콜릿 수를 추가하고 합계를 k로 나눕니다. 나머지가 0인 상태에서 완전히 나눈 경우 이 합계를 변수에 저장합니다. 더 나아가면서 최대 합을 얻을 때까지 이 과정을 반복합니다. 문제는 k로 나눌 수 있는 최대 합 하위 배열을 찾는 것입니다.
입력
Choco[]={ 1,2,4,5,2,8,3,5 } k=3 출력 −k명의 학생에게 균등하게 분배할 초콜릿의 최대 수 − 5
설명 − 최대 합 하위 배열은 { 5,2,8 }입니다. 초콜릿의 합은 15입니다. 똑같이 나누어 3명의 학생이 받을 수 있는 최대 초콜릿은 5입니다.
참고 - 상자는 연속적이고 인덱스는 { 3,4,5 }
입력
Choco[] = { 2,3,7,5,4,8,2,6 } k=5 출력 −k명의 학생에게 균등하게 분배할 초콜릿의 최대 수 − 7
설명 − 최대 합 하위 배열은 { 3,7,5,4,8,2,6 }입니다. 초콜릿의 합은 35입니다.
똑같이 나누어 5명의 학생이 모두 받는 최대 초콜릿은 7입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
우리는 연속적인 컨테이너에 많은 초콜릿을 포함하는 정수 배열 arr[]를 취합니다.
-
요소 수 'n'은 상자 수를 나타냅니다.
-
아니오. 입력으로 학생 'k'의 수.
-
maxChocolate( int arr[], int n, int k ) 함수는 배열, 크기 및 배열의 세 가지 인수를 취합니다. 학생 수 k.
-
for 루프를 사용하여 처음부터 arr[] 순회를 시작할 것입니다.
-
두 개의 변수 sum과 maxSum을 사용합니다. Sum은 하위 배열의 연속 요소 합계를 저장합니다.
-
maxSum은 지금까지 찾은 최대 합계를 저장하는 데 사용됩니다.
-
중첩된 for 루프 내부에서 요소를 계속 추가하고 sum%k가 나머지 0을 제공하는지 확인합니다.
또한 이 합계> maxSum인 경우 maxSum을 업데이트합니다.
-
결국 maxSum에는 최대 번호가 있습니다. k 학생에게 균등하게 나눌 수 있는 초콜릿의 수.
-
결과를 각 학생이 받는 초콜릿 수인 maxSum/k로 반환합니다.
예시
#include <stdio.h>
// to find the maximum number
// of chocolates to be distributed equally among
// k students
int maxChocolates(int arr[], int n, int k){
int sum;
int maxSum = 0;
for(int i=0;i<n;i++){
sum=0;
for(int j=i;j<n;j++){
sum+=arr[j];
if(sum%k==0 && sum>maxSum)
maxSum=sum;
}
}
// distributed equally among 'k' students
return (maxSum / k);
}
int main(){
int arr[] = { 2, 7, 6, 1, 4, 5 ,5, 3 };
int n =8;
int k =3;
printf("Maximum number of chocolates to be distributed equally among k students: %d ",maxChocolates(arr, n, k));
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Maximum number of chocolates to be distributed equally among k students − 11