백준 - 나머지 합 (10986)

10986번: 나머지 합

배열 A의 구간 합 중에 M으로 나누어 떨어지는 구간을 구하는 문제 입니다. "구간 합"이니까 누적합 배열을 만드는 것 까진 좋은데 여기서 해당 조건에 맞는 구간 찾는다고 일일히 경우의 수를 대입하면 (N(N-1))/2 = N^2이라는 시간이 걸리기 때문에 시간초과가 발생합니다.

 

다른 방법을 생각해 봐야 합니다. 우선 백준에 걸려 있는 예제를 봅시다.

5 3
1 2 3 1 2

5개의 요소가 주어진 배열에 3으로 나누어 떨어지느 구간합을 찾아야 합니다.

우선 누적합을 구해봅시다.

1 3 6 7 9

여기서 3으로 나누어떨어지는 수를 구하면

1 0 0 1 0

이렇게 됩니다.

 

누적합 배열에서 [i,j]구간의 부분합을 구하는 방법은 누적합 배열이 s라고 할 때, s[j] - s[i-1] 입니다. i가 0이라면 s[i-1]를 빼구요.

모듈러 연산까지 수행된 누적합에서 값이 0인 경우는 [0,i]까지의 구간합이 3에 나누어 떨어진 다는 것을 의미합니다. 따라서 s[i]값이 0인 경우가 총 3개 있으므로 일단 3가지의 경우의 수가 추가됩니다.

ans = 3

또한 s[i] - s[j-1]이 0인 경우. 즉, s[i] = s[j-1]인 경우도 역시 3으로 나누어떨어지는 경우가 됩니다. 즉, 나머지가 같은 인덱스 끼리 카운팅 한 다음 조합식을 이용해 나머지 경우의 수를 구할 수 있습니다. 예제에서는 0이 3개, 1이 2개 입니다.

ans = 3 + (3*2)/2 + (2*1)/2 = 7

즉 누적합을 미리 구하고, 누적합 배열중에 나머지가 같은 인덱스 끼리 카운팅 한 다음, 조합식으로 경우의 수를 구하면 됩니다. 0인 경우는 추가로 0의 갯수만큼 추가하면 되구요.

 

코드보기(C)

#include <stdio.h>
#define MAX (int)1e6

int main(void)
{
	int n, m, a[MAX], s[MAX], mod[(int)1e3];
	long long ans = 0;
	register int i;
	scanf("%d %d", &n, &m);

	for(i=0; i<n; i++)
	{
		scanf("%d", &a[i]);
		s[i] = (i == 0) ? a[i] : s[i-1] + a[i];
		s[i] %= m;
		mod[s[i]] += 1;
	}

	for(i=0; i<m; i++)
		ans += ((long long)mod[i] * (mod[i] - 1)) >> 1;
	ans += (long long)mod[0];

	printf("%lld\n", ans);
	return 0;
}

 

파이썬 너무 느려요... 어떻게 채점하는데 1분이 넘게 걸리지...