[백준/파이썬] 10986

https://www.acmicpc.net/problem/10986

골드 3 나머지 합  

💫 알고리즘

누적합 Prefix Sum

배열의 특정 구간 합을 빠르게 계산하기 위한 기법, 미리 누적된 값을 저장하여 활용

누적합 배열을 생성한 후, 구간 합을 O(1) 연산으로 빠르게 조회

쿼리 처리 속도가 매우 빨라짐

---

💡 풀이방향

🐢누적합과 모듈러 연산의 성질을 사용하여 모든 가능한 조합을 빠르게 계산

1️⃣ 주어진 A 배열의 누적합(prefix sum)을 계산

2️⃣ 모듈러 연산 적용

각 prefix sum을 M으로 나눈 나머지를 계산하여 배열에 저장

prefix sum P[i], P[j]가 같은 나머지를 가지면 P[j] - P[i]는 M의 배수가 되어 해당 구간의 합이 M으로 나누어 떨어짐

3️⃣ 나머지 빈도수 세기

같은 나머지를 가지는 두 인덱스가 있을 때, 그 사이의 구간 합이 M으로 나누어 떨어지므로
각 나머지별 등장 횟수를 기반으로 가능한 쌍의 수를 구할 수 있음

4️⃣ 유효한 구간 쌍의 개수 계산

나머지 r이 n번 등장한다면, 이 중 서로 다른 두 인덱스를 선택하는 경우의 수

: n * (n - 1) / 2

---

🌟 코드 구현 + 👀 풀이

[전체 코드]

import sys
input = sys.stdin.readline

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

r = [0] * M # 나머지 i가 등장한 횟수
pre_sum = 0 # 현재까지의 누적합

for i in range(N):
    pre_sum += A[i] # 현재까지의 누적합 계산
    r[pre_sum % M] += 1 # 누적합을 M으로 나눈 나머지 카운트

result = r[0]
for i in range(M):
    result += r[i] * (r[i] - 1) // 2

print(result)

 

r = [0] * M

누적합을 M으로 나눈 나머지 i가 나온 횟수를 저장하는 배열

 

누적합 계산 + r(나머지) 카운트

for i in range(N):
    pre_sum += A[i]  # 현재까지의 누적합 계산
    r[pre_sum % M] += 1  # 누적합을 M으로 나눈 나머지를 카운트

 

연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수

result = r[0]
for i in range(M):
    result += r[i] * (r[i] - 1) // 2

🤔 왜 r[0]을 먼저 더하나요?

🐢 누적합 자체가 M의 배수인 경우라서요. 

🤔 nC2, 즉 result += r[i] * (r[i] - 1) // 2는 왜 하는 건가요?

🐢 같은 나머지가 두 번 이상 등장할 경우, 서로 다른 두 인덱스를 골라서 빼면 M의 배수가 되어 해당 구간의 합이 M으로 나누어 떨어지기 때문이에요. 이해를 위해 예시를 들어볼게요!!

r[0]에 들어갈 수 있는 누적합은 1 + 2(=3), 1 + 2 + 3(=6), 1 + 2 + 3 + 1 + 2(=9)가 있죠?

[1 + 2 + 3] - [1 + 2] = 3, [1 + 2 + 3 + 1 + 2] - [1 + 2 + 3] = 1 + 2 = 3

[1 + 2 + 3 + 1 + 2] - [1 + 2 + 3] = 1 + 2 = 3

으로 서로 다른 두 인덱스를 골라서 빼면 부분 구간의 합이 M으로 나누어 떨어지게 돼요. 

그래서 result에 서로 다른 두 인덱스를 고르는 경우의 수를 더하는 거죠!