나머지 합 구하기(백준 10986)

문제

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

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

 

입력

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

둘째 줄에 N개의 수 $A_1, A_2, ..., A_N$이 주어진다. (0 ≤ $A_i$ ≤ $10^9$)

 

출력

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

 

입출력

5 3
1 2 3 1 2

7

 

💡 문제 상황 이해하기 
입력 5 3
- 5 : 수의 개수
- 3 : 3 으로 나누어 떨어지는 구간이 있는지

입력 1 2 3 1 2 에서 연속된 부분의 합이 3으로 나누어 떨어지는 구간
- 1 2 3 1 2 : (1 + 2 가 3으로 나뉘어 떨어짐)
- 1 2 3 1 2 
- 1 2 3 1 2 
- 1 2 3 1 2 : (2 + 3 + 1 이 3으로 나뉘어 떨어짐)
- 1 2 3 1 2 
- 1 2 3 1 2 
- 1 2 3 1 2 

 

나머지 합의 핵심 아이디어
1. (A + B) % C = ((A % C) + (B % C)) % C 
  ex) ((1 % 3) + (2 % 3 )) % 3 = 0
        (1 + 2) % 3 = 0

2. S[i] % M의 값과 S[j] % M의의 값이 같다면, (S[i] - S[j]) % M은 0이다.
  ex)
  A = [3, 2, 4, 5, 1]
  A의 합배열 S = [3, 5, 9, 14, 15] 여기서 M을 3으로 가정하고 각 부분을 나머지를 확인하면 [0, 2, 0, 2, 0]
 
  구간 한 배열의 원소를 M으로 나눈 나머지로 업데이트 하고 S[i]와 S[j]가 같은 (i,j)쌍을 찾으면 원본 리스트에서 i + 1 부터
  j 까지의 구간의 합이 M으로 나누어 떨어진다.
  ex)
  합 배열의 나머지 배열 S = [0, 2, 0, 2, 0] 에서 나머지가 같은 S[1], S[3]에서 S[3] - S[1]은 3으로 나누어 떨어지는데,
  S[3] - S[1] 은 원본 데이터의 A[4, 5] 부분이다.
  나누어 떨어지는 이유는 원본에서 S[3]은 A[3, 2, 4, 5]의 합이고 나머지는 2이다, S[1]은 A[3, 2]의 합이고 나머지는 2이다.
  [3, 2] 부분이 상쇄되므로 3으로 나누어 떨어지게 된다.
  

※ S[i] : 합배열
- A[1 , 2, 3] 이라는 배열의 합 배열은 S[1, 3, 6]

 

여기서 나누어 떨어지는 모든 구간을 풀이하는 순서

1. 합배열에서 M으로 나누어 떨어지는 부분

2. 합배열에서 나머지가 같은 원소 2개를 뽑는 모든 경우의 수

 

코드

n, m = map(int, input().split()) 

A = list(map(int, input().split())) #원본
S = [] #합배열

C = [0]*m 
#같은 나머지의 인덱스를 카운트, m보다 큰 값을 가질 수는 없으므로 m만큼 초기화

sum = 0
result = 0

for i in A:
    sum = sum + i
    S.append(sum)


for i in S:
    temp = i % m
    if temp == 0:
        result += 1
    
    C[temp] += 1
    

for i in range(m):
    if C[i] > 1:
        result += (C[i] * (C[i] - 1) // 2) # 나누기 연산 시 float 형태가 되는 것 조심

print(result)