문제 개요
이 문제에서는 크기가 n인 배열과 정수 m이 주어집니다. 우리의 과제는 C++로 배열의 모든 부분 배열(subarray) 합을 m으로 나눈 나머지(modulo) 중 가장 큰 값을 찾는 프로그램을 작성하는 것입니다.
프로그램 설명 − 여기서는 부분 배열의 모든 요소 합을 m으로 나누었을 때 얻을 수 있는 나머지 값 중 최대값을 구합니다.
예시로 문제 이해하기
입력 − arr[] = {4, 9, 2}, m = 6
출력 − 5
설명 − 가능한 모든 부분 배열과 각각의 나머지 값은 다음과 같습니다.
{4}: 4 % 6 = 4
{9}: 9 % 6 = 3
{2}: 2 % 6 = 2
{4, 9}: 13 % 6 = 1
{9, 2}: 11 % 6 = 5
{4, 9, 2}: 15 % 6 = 3위 결과 중 가장 큰 나머지 값은 5이므로 정답은 5입니다.
접근 방법
이 문제를 효율적으로 해결하려면 접두사 합(prefix sum)의 모듈로 값을 활용합니다. 먼저 각 인덱스까지의 누적 합을 m으로 나눈 나머지(prefixSumModulo)를 계산합니다.
부분 배열 arr[j+1..i]의 합 modulo m은 다음 공식으로 표현할 수 있습니다.
maxSum at i = (prefix[i] − prefix[j] + m) % m
이 값이 최대가 되려면 현재 prefix[i]보다 바로 다음으로 큰 prefix[j]를 찾아야 합니다. 이를 위해 std::set의 lower_bound() 함수를 사용하면 정렬된 상태에서 원하는 값을 빠르게 탐색할 수 있으며, 전체 시간 복잡도는 O(n log n)으로 브루트 포스 방식(O(n²))보다 훨씬 효율적입니다.
구현 예제
위 접근 방식을 구현한 프로그램은 다음과 같습니다.
#include<bits/stdc++.h>
using namespace std;
int calcMaxSum(int arr[], int n, int m) {
int prefix = 0, maxSumMod = 0;
set<int> sums;
sums.insert(0);
for (int i = 0; i < n; i++) {
prefix = (prefix + arr[i]) % m;
maxSumMod = max(maxSumMod, prefix);
// prefix보다 큰 값 중 가장 작은 값 탐색
auto it = sums.lower_bound(prefix + 1);
if (it != sums.end())
maxSumMod = max(maxSumMod, prefix - (*it) + m);
sums.insert(prefix);
}
return maxSumMod;
}
int main() {
int arr[] = {4, 9, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int m = 5;
cout << "Maximum subarray sum modulo " << m
<< " is " << calcMaxSum(arr, n, m) << endl;
return 0;
}
실행 결과
Maximum subarray sum modulo 5 is 4
복잡도 분석
- 시간 복잡도: O(n log n) — 각 요소마다 set에 대한 삽입 및 탐색(log n)이 수행됩니다.
- 공간 복잡도: O(n) — 접두사 합의 나머지 값을 저장하기 위한 set이 필요합니다.
마무리
모듈로 연산이 포함된 최대 부분 배열 합 문제는 단순 카데인 알고리즘(Kadane's Algorithm)으로는 해결할 수 없습니다. 음수가 아닌 나머지 값의 특성을 고려해 접두사 합과 균형 탐색 트리(set)를 결합하면 효율적으로 최적해를 구할 수 있습니다. 이 기법은 나머지 연산이 등장하는 다양한 최적화 문제에도 응용될 수 있으니 꼭 숙지해 두시기 바랍니다.