[백준] 10986 (나머지 합)

구간합 다른 문제 구간합1  구간합2

10986

10986번: 나머지 합

🐲접근

(A+B) % C = ((A%C)+(B%C))%C

해당 구간 합의 나머지 연산 값 = 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값 

합 배열 S 가 있다고 할 때,
S[i] % M == S[j]%M 이면 (S[i] + S[j])%M == 0 

: 구간 합 배열의 원소를  M으로 나눈 나머지로 업데이트하고  S[i]  와 S[j] 가 같은 (i,j) 쌍을 찾으면 원본 리스트에서  i+1부터 j 까지의 구간 합이 M으로 나누어 떨어짐. 

풀이

코드

import sys
input = sys.stdin.readline
from itertools import combinations

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

#원본 배열
A = list(map(int,input().split()))

# 합배열
S = [0]* N

# 나머지 값이 같은 인덱스 수 저장하는 리스트
C = [0] * M  # M보다 작은 수로 나머지 생성됨으로 그 만큼 길이의 나머지 리스트 생성

S[0] = A [0]

# 결과값 카운팅
cnt = 0

# 합 배열 만들기 
for i in range(1,N):
    S[i] = S[i-1] + A[i]

# 합 배열을 M으로 나눈 나머지 값으로 업데이트 
for i in range(N):
    remainder = S[i]%M
    if remainder == 0 :
        cnt += 1
    C[remainder] += 1  #나머지 값이 같은 인덱스 개수 업데이트
 
# 나머지 값이 같은 인덱스 중 2개를 뽑은 경우의 수 더하기    
for i in range(M):
    if C[i] > 1:
        cnt += (C[i]*(C[i]-1)//2) #조합 공식
    
print(cnt)

## 과정 보기
5 3
1 2 3 1 2

[1, 0, 0, 1, 0] # 합 배열 업데이트 후 모습 (코드 상으로는 구현하지 않음)

# 배열 C 변화 과정 보기 
[0, 1, 0] # 나머지 1 카운트 
[1, 1, 0] # 나머지 0 카운트
[2, 1, 0] # 나머지 0 카운트
[2, 2, 0] # 나머지 1 카운트
[3, 2, 0] # 나머지 0 카운트