[알고리즘 코딩테스트](2)자료구조-2: 구간 합(3)

[문제5] 나머지 합 구하기

N개의 수 A1,A2,..., An이 주어졌을 때 연속된 부분의 합이 M으로 나누어떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉  Ai+...+...Aj(i<=j)의 합이 M으로 나누어 떨어지는 (i,j)쌍의 개수를 구하시오.

 

입력

1번째 줄에 N과 M(1<=N<=106, 2<=M<=103), 2번째 줄에 N개의 수 A1,A2,...,An이 주어진다. (0<=Ai<=109)

 

예제 입력

5, 3

1 2 3 1 2 

 

예제 출력

7

 

문제 분석하기

1)(A+B)%C는 ((A%C)+(B%C))%C와 같다. 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.

 

2)S[i]-S[j]는 원본 리스트의 j+1 부터 i까지의 구간 합이다

 

3)S[i]%M의 값과 S[j]%M의 값이 같다면 (S[i]-S[j])%M은 0이다.

 

손으로 풀어보기

 

1)리스트 A의 합 배열 S의 생성

• 리스트A

1

2

3

1

2

• 합 배열 S

1

3

6

7

9

2)합 배열의 M(3) 나머지 연산 수행

1

0

0

1

0

3) 경우의 수 계산

• 원소 값이 0인 개수 :3
• 나머지 값이 동일한 경우: 1로 동일한 경우 2가지, 0으로 동일한 수 3가지

4) 최종 결론

3 + 2C2 + 3C2 =7

 

코드

import sys
input=sys.stdin.realine
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):
    remainer=S[i]%m
    if(remainer)==0:
        answer += 1
    C[remainer] += 1

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

연습 코드

n=5
m=3

A=[1,2,3,1,2]

S=[0]*n
C=[0]*m #나머지로 올 수 있는 값은 0,1,2 로 m과 동일함
print(S)
print(C)
S[0]=A[0]
answer=0
print(S) #[1,0,0,0,0]

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

print(S) #[1,3,6,7,9] 합 배열 저장

for i in range(n):
  remainer=S[i]%m
  if remainer ==0:
    answer += 1
  C[remainer] += 1  
print(answer) #3
print(C) #[3,2,0] 나머지가 0인경우 3, 1인경우 2, 2인 경우 0

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

print(answer) #7