백준 10986[나머지 합]

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으로 나눈 나머지가 같은 쌍을 찾으면 원본 리스트에서 j+1부터 i까지의 구간 합이 M으로 나누어 떨어짐

1. 합 배열 생성
2. 합 배열을 m으로 나눠 합 배열 업데이트
3. 원소값이 0인 갯수 세기
4. 원소 값이 같은 인덱스의 개수 콤비네이션 2 구해서 더해주기

2. 슈도코드 작성

n(숫자의 개수), m(나눌 수) 정수로 입력받기
A(원본 배열) 리스트로 입력받기
S(합 배열) 생성해놓기
C(콤비네이션용, 같은 나머지 인덱스 카운트용 리스트) 생성
tmp = 원본 배열 합 저장용 변수
cnt 변수 생성(정답 출력용)

for i -> n까지:	
	tmp += A[i]
    S에 추가

for i -> n까지:
	x = S[i] % m
  	if x가 0이면
    	cnt변수 1증가
    C[x]값을 1증가
    
for i -> m까지:
	C[i]에서 2가지 뽑는 경우의 수를 정답에 더하기
    
출력

3. 코드 구현

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
A = list(map(int, input().split()))
S = [0] * n
C = [0] * m
S[0] = A[0]
answer = 0

for i in range(1, n):
    S[i] = S[i-1] + A[i]

for i in range(n):
    x = S[i] % m
    if x == 0:
        answer += 1
    C[x] += 1

for i in range(m):
    if C[i] > 1:
        answer += (C[i] * (C[i] - 1) // 2)

print(answer)