[백준/자바] 10986 나머지 합

10986 나머지 합 사진 클릭시 문제로 이동

---

문제

수 N개 A1, A2,..., AN이 주어진다.

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

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

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

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

출력

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

예제 입력 1

5 3
1 2 3 1 2

예제 출력 1

7

---

알고리즘 분류

• 누적 합

---

설명 

M으로 나눠지는 구간 합의 개수를 구하는 문제다.

첫 번째 수부터 i까지의 구간 합을 Si라 하자.

첫 번째 수부터 j까지의 구간 합을 Sj라 하자.

 

i부터 j까지의 구간합은 Sj - S(i-1)이 된다.

index	0	1	2	3	4	5
num[index]	비워둠	1	2	3	1	2
구간 합	0	1	3	6	7	9

index 1부터 3까지의 구간합은 S3 - S(1-1) = S3 - S0 = 6이 되는 것을 볼 수 있다.

 

문제는 구간합이 M으로 나누어 떨어지는 즉 0이 되어야 한다.

이 말은 다시 말해서 i부터 j까지의 구간합인 Sj - S(i-1)이 M으로 나누어 떨어진다는 의미가 된다.

{Sj - S(i-1)}% M = 0
<=> Sj% M = S(i-1)% M

이 말은 i까지의 구간 합의 나머지와 j까지의 구간 합의 나머지가 같다는 소리다.

나머지가 같은 구간 합의 개수 중 2개를 뽑아 다 더하면 된다.

 

M으로 나눌 때 나올 수 있는 나머지는 0, 1,..., M-1이다.

즉, 나머지가 0인 구간 합의 개수 중 2개를 뽑는 경우의 수 +

나머지가 1인 구간 합의 개수 중 2개를 뽑는 경우의 수 +... +

나머지가 M-1인 구간 합의 개수 중 2개를 뽑는 경우의 수

를 구하면 된다.

 

여기서 주의해야 할 점은 구간 합이 0인 지점은 그 자체로도 즉 1개 만으로도 답이 될 수도 있기 때문에 따로 더해야 한다는 점이다.

코드