1. 문제

---

출처: 백준 10986번 나머지 합

2. 풀이

---

모듈러 연산은 더하기, 빼기를 하기 전에 미리 해도 유지되는 장점이 있다.

(A-B) % M = ((A % M) - (B % M)) % M

그리고 연속된 부분 구간의 합을 쭉 DP 형태로 저장해두고, 특정 구간의 합을 구할 때는 그 DP 값을 서로 빼는 형태로 구할 수 있다. 관련된 풀이를 백준 11659번 구간 합 구하기 4에서 한 적이 있다.

따라서, 이번에는 단순히 구간 합을 저장하는 것이 아니라 M에 대한 모듈러 연산을 한 값을 저장하는 식으로 문제에 접근한다.

M으로 나눈 나머지는 0~(M-1)까지 존재할 수 있으며, 연속된 부분 구간 합에 대해 각 나머지가 나오는 개수를 DP로 세주면 된다.

그리고 같은 나머지 값을 가지는 것을 2개씩 뽑아 빼기를 진행하면 되므로, 각 개수에 대해 2개씩 뽑는 조합을 계산하면 된다. 이때, 나머지가 0이면 꼭 빼기를 진행하지 않고 하나만 골라도 괜찮으므로, dp[0]은 숫자를 하나 더 해준다.

3. 소스코드

---

N, M = map(int,input().split())

num = list(map(int,input().split()))

dp = [0]*M
dp[0] = 1
total = 0

for i in range(N):
    total += num[i]
    r = total % M
    dp[r] += 1

count = 0
for i in dp:
    count += i*(i-1)//2
    
print(count)

4. 그 외

---

다시금 문제를 봐도 생소하게 느껴지는 걸 보면, 많은 생각을 요구하는 문제라고 느껴진다.