https://www.acmicpc.net/problem/10986
문제 풀이
누적합 알고리즘 다시 리마인드하자.
i부터 j번째까지의 누적합은
S[j] - S[i-1] 로 구할 수 있었다.
그리고 나머지 연산의 중요한 성질도 알아야 한다.
어떤 수 A와 B에 대해, (A - B)가 M으로 나누어떨어진다면,
즉 (A - B) % M == 0 이라면, A % M == B % M 이다.
예를 들어, A = 13, B = 7, M = 6일 때,
13 - 7 = 6 → 6은 6으로 나누어떨어짐
그리고 13 % 6 = 1, 7 % 6 = 1 → 나머지가 같다
이 성질을 누적합 알고리즘에 접목해보자.
"어떤 구간합이 M으로 나누어떨어진다는 것은,
해당 구간 양 끝 누적합의 나머지가 같다는 뜻이다."
→ 거꾸로 말하면,
"두 누적합의 나머지가 같다면, 그 사이 구간합은 M으로 나누어떨어진다!"
외우자 그냥
로직 요약
1. 누적합을 M으로 나눈 나머지를 계속 저장한다.
2. 같은 나머지를 가진 누적합 쌍의 개수를 세고,
그 중 2개를 고르는 조합(nC2) 만큼이 M으로 나누어떨어지는 구간합이 된다.
3. 나머지가 0인 경우는,
시작부터 해당 인덱스까지의 구간 자체가 M으로 나누어떨어지는 경우이므로,
처음부터 따로 1씩 카운팅한다 (또는 mod_count[0]을 1로 초기화한다).
import sys
input = sys.stdin.readline
# N: 숫자 개수, M: 나눌 값
N, M = map(int, input().split())
A = list(map(int, input().split()))
# 누적합의 나머지를 카운트할 배열 (0~M-1까지)
mod_count = [0] * M
mod_count[0] = 1 # 누적합이 처음부터 나누어떨어지는 경우 (sum % M == 0)
prefix_sum = 0
for num in A:
prefix_sum += num # 누적합 계속 더하기
remainder = prefix_sum % M # M으로 나눈 나머지
mod_count[remainder] += 1 # 나머지 개수 증가
# 이제 같은 나머지를 가진 것들 중 2개를 고르는 경우의 수 계산
result = 0
for count in mod_count:
# 조합 공식: nC2 = n(n-1)//2
result += count * (count - 1) // 2
print(result)
Frontend Engineers