🚩 코딩테스트/알고리즘
[백준] 10986번: 나머지 합
딩딩크롱
2023. 5. 9. 23:19
728x90
문제
https://www.acmicpc.net/problem/10986
10986번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
풀이
누적합을 사용해 풀었습니다.
ramainder에 누적합의 나머지 개수를 저장합니다.
\(_{i}{C}_{2}\) 를 계산해 answer에 더합니다.
코드
파이썬
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
total = 0
remainder = [0] * M
for i in range(N):
total += A[i]
remainder[total % M] += 1
answer = remainder[0]
for i in remainder:
answer += (i * (i-1)) // 2
print(answer)728x90