python 10986 나머지 합 구하기

📌 문제 정보

• 문제 번호: 10986
• 문제: https://www.acmicpc.net/problem/10986
• 난이도: 골드 3

---

🧩 문제 요약

정수로 이루어진 수열이 주어졌을 때, 부분합의 나머지가 M으로 나누어떨어지는 경우의 수를 구하는 문제임.

부분합이란 i~j 구간의 합을 의미하며, 이 구간의 합이 M으로 나누어떨어질 때를 모두 세야 함.

---

🧪 예제 입력 / 출력

입력: 5 3 1 2 3 1 2

 

출력: 7

• 누적합 기준으로 구간을 잡을 때, 나머지가 0이 되는 경우가 7가지 존재함.

---

💡 접근 방식

• 단순히 모든 구간을 탐색하면 시간 초과 → 누적합 + 나머지 개념 활용
• 누적합을 계산한 뒤, 같은 나머지를 가지는 구간의 조합 수를 이용하여 계산함
• 나머지가 같다는 것은 두 구간 사이의 차이가 M으로 나누어떨어진다는 의미

---

⚙️ 알고리즘 설명

1. 누적합 배열을 만든 후 각 누적합을 M으로 나눈 나머지를 저장함
2. 누적합 자체가 M으로 나누어떨어지면 바로 정답에 추가함
3. 같은 나머지를 가진 누적합의 개수를 세어 조합 공식 nC2 = n*(n-1)//2로 더함
4. 이유: 누적합 A, B가 있고 A ≡ B (mod M)일 때, A~B 구간은 M으로 나누어떨어짐

---

🧑‍💻 코드 구현 (Python)

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
nums = list(map(int, input().split()))
sums = [0] * N  # 누적합 배열
check = [0] * M  # 나머지 카운트 배열

sums[0] = nums[0]
answer = 0

# 누적합 계산
for i in range(1, N):
    sums[i] = sums[i - 1] + nums[i]

# 누적합의 나머지에 따라 카운팅
for i in range(N):
    checker = sums[i] % M
    if checker == 0:
        answer += 1  # 0으로 나누어떨어지는 경우는 바로 추가
    check[checker] += 1  # 나머지 카운트

# 같은 나머지를 가진 누적합 조합 계산
for i in range(M):
    if check[i] > 1:
        answer += (check[i] * (check[i] - 1) // 2)

print(answer)

---

🔁 다른 풀이 / 코드 개선 방향

• sums 배열 없이도 처리 가능. 누적합을 바로 계산하면서 나머지를 바로 카운트하면 메모리 절약 가능
• 개선된 코드 예:

import sys
input = sys.stdin.readline

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

prefix_sum = 0
count = [0] * M
answer = 0

for num in nums:
    prefix_sum = (prefix_sum + num) % M
    if prefix_sum == 0:
        answer += 1
    count[prefix_sum] += 1

for c in count:
    if c > 1:
        answer += (c * (c - 1)) // 2

print(answer)

---

⏱️ 시간복잡도 분석

• 시간복잡도: O(N)
  • 한 번의 반복으로 누적합 및 나머지 처리 가능
• 공간복잡도: O(M)
  • 나머지 카운트 배열 check 사용

---

📝 결론 및 팁

• 누적합 + 나머지를 활용한 모듈로 누적합 트릭이 핵심
• 부분합을 직접 계산하지 않고 차이로 구간합 성립 여부를 판단하는 것이 포인트
• 자주 나오는 유형이므로 반드시 숙지해야 함

📌 유사 문제 추천:

• 11659번 구간 합 구하기 4 : https://www.acmicpc.net/problem/11659
• 1546번 평균 : https://www.acmicpc.net/problem/1546
• 2015번 수들의 합 4 : https://www.acmicpc.net/problem/2015