[백준] 10986번 - 나머지 합

---

문제 분석

N의 최댓값이 106개로 모든 구간 합을 구해야 하므로 1초 안에 연산하기는 어렵다. 따라서 구간 합 배열을 이용하여 해결한다.

나머지 합 문제 풀이의 핵심 아이디어

• (A + B) % C는 ((A % C) + (B % C)) % C와 같다. 다시 말해 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.

• 구간 합 배열을 이용한 식 S[i] - S[j]는 원본 리스트의 j + 1부터 i까지의 구간 합이다.

• S[i] % M의 값과 S[j] % M의 값이 같다면 (S[i] - S[j]) % M은 0이다. 즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트 하고 S[i]와 S[j] 같은 (i,j)쌍을 찾으면 원본 리스트에서 j + 1부터 i까지의 구간 합이 M으로 나누어떨어진다는 것을 알 수 있다.

---

소스 코드

# 나머지 합

import sys
input = sys.stdin.readline

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

arr = [0]*(N+1)  # 입력 받은 배열
sumArr = [0]*(N+1)  # 구간 합 배열
left = [0]*M  # 나머지 값이 동일한 값들의 개수 (인덱스는 나머지 값을 의미함)
count = 0  # 정답 개수

for i in range(1, N+1):
    arr[i] = numList[i-1]
    sumArr[i] = sumArr[i-1] + arr[i]

for i in range(1, N+1):
    value = sumArr[i] % M
    if value == 0:
        count += 1
    left[value] += 1

for i in range(M):
    if left[i] > 1:
        count += (left[i] * (left[i]-1)) // 2

print(count)