[BOJ] #10986번: 나머지 합

 

 

문제

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

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

 

입력

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

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

 

출력

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

 

예제 입력 1

5 3
1 2 3 1 2

예제 출력 1

7

 

 

풀이

단순 부분합을 이용해서는 풀 수 없다. N이 10^6까지 주어질 수 있기 때문에 효율의 효율의 효율을 추구해야 한다.

(1) 누적합을 구한다.

(2) m으로 나눠서 나머지 리스트를 만든다.

(3) 나머지가 같은 것끼리 빼면 나머지는 0이 되고, 하나의 구간이 나온다.

 

수가 크게 나오면  단순 list로 메모리를 감당할 수 없다. Zero list를 써서 하나의 리스트에 나머지와 리스트 순번을 모두 담았다.

 

 

import sys
n, m = map(int, sys.stdin.readline().split())
n_list = list(map(int, sys.stdin.readline().split()))


# 1. 누적합 list, 나머지 list 구성하기
import itertools
sum_list = list(itertools.accumulate(n_list))
remain = [0] * (m+1)
for t in sum_list:
    remain[t%m] += 1


# 2. 리스트업하기
a = 0
for s in range(len(remain)):
    m_len = remain[s-1]
    num = 1
    while m_len - num > 0:
        a += m_len - num
        num += 1
    if s == 0:
        a += m_len
a += remain[0]


# 3. 출력하기
print(a)