[백준/자바] 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개 만으로도 답이 될 수도 있기 때문에 따로 더해야 한다는 점이다.