[C] 백준 10986번 나머지 합

링크
https://www.acmicpc.net/problem/10986

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 10^9)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

예제 입력 1

5 3
1 2 3 1 2

예제 출력 1

7

아이디어 스케치

• 처음에는 누적 합 배열을 만들어 누적 합을 저장해놓고 누적 합의 인덱스 범위를 하나씩 늘리면서 M의 배수가 되었을 때 카운트 하는 알고리즘을 구현했지만 시간 초과가 발생했다.
• 이 문제를 위와 같이 풀었을 때 시간 복잡도는 O(n^2)이 되는데 이 문제는 시간 복잡도를 이것보다 줄여야 한다.
• 시간 복잡도를 줄이는 방법은 모듈러 연산을 이용하는 방법이 있는데 모듈러 연산에서는 이와 같은 성질이 만족한다.
  • (A+B)%C = (A%C)+(B%C)
  • (A-B)%C = (A%C)-(B%C)
  • (AXB)%C = (A%C)X(B%C)
  • (A/B)%C = (A%C)/(B%C)
• 먼저 위 식에 적용해보면 위 식의 누적 합은 1,3,6,7,9 이고 모듈러 3 연산을 수행하면 1,0,0,1,0 이 된다.
• 우리는 배열 인덱스 i~j사이의 값의 누적합이 모듈러 3 연산을 수행했을 때 0이 나오는 갯수를 구하는 것이다.
• j-i = 0일 때 자기자신 즉, 범위가 1일 때 모듈러 3이 0인 갯수가 3개이다.
• 0이 3개인 경우에서 i와j를 뽑아야 하는데 j가 i보다 크거나 같으므로 순서와 상관있게 2개를 뽑아야한다. 즉 3C2개의 경우의 수가 나온다.
• (j까지의 누적합%3) - (i까지의 누적합%3)=(i부터 j까지의 누적합)%3=0 인 경우에도 카운팅을 해야하는데 위에 1이 2개가 있으므로 순서가 상관있고 2개중 2개를 뽑아야 하므로 2C2개의 경우의 수가 나온다.
• 결과적으로 3+3+1=7개가 나온다.
• 위 알고리즘으로 구현하면 문제에서 제시하는 시간복잡도를 만족할 수 있다.

코드 분할 설명

typedef long long ll;

int N, M;
ll result;
ll tmp;
ll* arr;

• 위에서 주어지는 변수의 값의 범위를 보면 요소별 10^9이하의 크기의 숫자가 N(10^6개)개 만큼 주어지는데 이 값의 누적 합을 구하는 과정에서 int형의 최대 크기를 훨씬 초과하기 때문에 long long 자료형으로 선언해줘야한다.

for (int i = 1; i <= N; i++) {
	scanf("%lld", &arr[i]);
	arr[i] += arr[i - 1];
	arr[i] %= M;
	cnt[arr[i]]++;
}

• 값을 하나씩 입력받고 누적 합을 구하면서 이 누적 합을 M에 대하여 모듈러 연산을 수행한 후 각 나머지 별 갯수를 저장한다.

result = cnt[0];

for (int i = 0; i < M; i++) {
	tmp = cnt[i];
	result += tmp * (tmp - 1) / 2;
}

printf("%lld", result);

• result 변수에 위에서 말한 범위가 1인 누적 합에서 나머지가 0인 갯수를 저장한다.
• 나머지가 i인 갯수 중에서 순서를 고려하여 2개를 뽑는 iC2를 수행하고 이 값을 result에 더한다.
• 결과를 출력한다.

전체 코드

#include <stdio.h>
#include <stdlib.h>

typedef long long ll;

ll cnt[1001];

int main()
{
	int N, M;
	ll result;
	ll tmp;
	ll* arr;
	scanf("%d %d", &N, &M);

	arr = (ll*)calloc(N+1, sizeof(ll));

	for (int i = 1; i <= N; i++) {
		scanf("%lld", &arr[i]);
		arr[i] += arr[i - 1];
		arr[i] %= M;
		cnt[arr[i]]++;
	}

	result = cnt[0];
	
	for (int i = 0; i < M; i++) {
		tmp = cnt[i];
		result += tmp * (tmp - 1) / 2;
	}

	printf("%lld", result);

	free(arr);

	return 0;
}

제출 결과