연속된 상자에 들어 있는 초콜릿의 개수가 배열 형태로 주어지고, 이 초콜릿을 나눠 받을 학생 수 k가 함께 주어집니다. 우리가 해야 할 일은 연속된 상자들을 선택하여 그 안에 든 초콜릿의 합이 k명의 학생에게 정확히 똑같이 나누어질 수 있도록 하는 것이며, 동시에 그 합이 최대가 되도록 만들어야 합니다.
이 문제는 본질적으로 k로 나누어떨어지는 최대 합 부분 배열(maximum sum subarray divisible by k)을 찾는 문제입니다. 배열을 왼쪽에서 오른쪽으로 순회하면서 초콜릿 개수를 차례로 더하고, 그 합을 k로 나눕니다. 나머지가 0으로 완전히 나누어떨어진다면 해당 합을 변수에 저장합니다. 이 과정을 반복하며 탐색 범위를 넓혀 가면, 결국 조건을 만족하는 최대 합을 구할 수 있습니다.
입력 예시 1
Choco[] = { 1, 2, 4, 5, 2, 8, 3, 5 }, k = 3출력: 학생 한 명당 받을 수 있는 최대 초콜릿 개수 — 5개
설명: 합이 최대가 되는 부분 배열은 { 5, 2, 8 }입니다. 초콜릿의 총합은 15개이며, 이를 3명에게 균등하게 나누면 각 학생이 5개씩 받게 됩니다.
참고: 상자는 연속되어야 하며, 해당 상자들의 인덱스는 { 3, 4, 5 }입니다.
입력 예시 2
Choco[] = { 2, 3, 7, 5, 4, 8, 2, 6 }, k = 5출력: 학생 한 명당 받을 수 있는 최대 초콜릿 개수 — 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, 즉 학생 한 명이 받게 되는 초콜릿 개수를 결과로 반환합니다.
C 언어 구현 예제
#include <stdio.h>
// k명의 학생에게 균등하게 분배할 수 있는
// 초콜릿의 최대 개수를 구하는 함수
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;
}
}
// k명의 학생에게 균등 분배
return (maxSum / k);
}
int main(){
int arr[] = { 2, 7, 6, 1, 4, 5 ,5, 3 };
int n =8;
int k =3;
printf("k명의 학생에게 균등하게 분배할 수 있는 초콜릿의 최대 개수: %d ",maxChocolates(arr, n, k));
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
k명의 학생에게 균등하게 분배할 수 있는 초콜릿의 최대 개수 — 11
이 예제에서 배열 { 2, 7, 6, 1, 4, 5, 5, 3 }의 전체 합은 33이고, 이를 3으로 나누면 나머지가 0이므로 모든 상자를 선택할 수 있습니다. 따라서 각 학생은 11개의 초콜릿을 받게 됩니다.