나머지 합

나머지 합 구하기 (백준 10986번, 시간 제한: 1초)

문제
수 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으로 나누어 떨어지는 구간의 개수를 출력한다.

입력 예시
5 3
1 2 3 1 2

출력 예시
7

코드 예시

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=list(map(int,input().split()))
temp_sum=[]
temp_sum.append(arr[0]%m) #temp_sum %m 합 배열
temp=arr[0]
ans=0
c=[0]*m
for i in arr[1:n+1]:
    temp+=i
    temp_sum.append(temp%m)
for i in temp_sum:
    if i==0:
        ans+=1
    c[i]+=1 #같은 mod sum 개수 count 배열
for i in c: 
    if i > 1:
        ans+=(i*(i-1))//2 #nC2, //을 사용하여 정수계산
print(ans)

이 문제는 생각보다 어려웠다.
우선 m 으로 나눈 나머지 합 배열을 가지고 있어야 한다.
1 0 0 1 0
이렇게 temp_sum 이 있으면
0 의 개수 먼저 세보자.
해당 부분까지의 합이 m 으로 나누어 떨어진다는 뜻이기 때문이다.

추가적으로 temp_sum 에서 같은 값들을 2개 골라 nC2 를 계산한다.
temp_sum[i]%m==temp_sum[j]%m
이면 (temp_sum[j]-temp_sum[i])%m==0 이기 때문에 해당 A[i+1]~A[j] 인 부분 합 구간이 m 으로 나누어 떨어진다.

'//' 을 사용해서 소수점 나눗셈이 아닌 정수형 나눗셈으로 구한다.