[백준/파이썬] 10986번 나머지 합 구하기

---

※ 문제

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)

※ 출력

1번째 줄에 연속된 부분의 합이 M으로 나누어떨어지는 구간의 개수를 출력한다.

 

 

※ 해결방법

이 문제를 해결하기 위해서는 먼저 리스트의 구간 합 알고리즘을 사용하여야한다. 

 

리스트 A가 있을 때 합 배열 S는 다음과 같이 정의하는데,

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]

이를 단순화 하면

S[i] = S[i-1] + A[i] 

이를 활용하면 합 배열을 미리 구해 두었을 시에, 구간의 합을 손쉽게 구할 수 있다는 의미가 된다.

 

• 먼저 합 배열 S를 구하고 M값으로 나머지 연산을 수행한다.

만약 M값으로 나눈 나머지 값이 0이라면 처음부터 i값을 모두 더한 부분의 값이 조건에 부합하는 것을 알 수 있다.

• 예를 들어  1 2 3 1 2 이라는 값이 주어졌다면 합 배열은 1 3 6 7 9 이다. 그리고 M값이 3이라고 가정을 한다면, 나머지의 배열은 1 0 0 1 0 이 된다.  

S[1]과 S[2] S[4]는 각각 조건에 만족하는 것이다. 또한 S[2] - S[1] , S[4] - S[1] , S[4] - S[2]도 또한 나머지 값이 0이므로 조건에 만족한다는 것을 알 수 있다. 그러므로 나머지가 0인 것들을 2개를 뽑아서 계산할 수 있도록 nC2의 공식을 사용하면 된다. 

물론 나머지가 1인 S[3] - S[0]도 나머지의 값이 0이 되는 것을 알 수 있으므로, 나머지가 같은 것들끼리 2개를 골라서 nC2의 값을 적용해주면 된다!

 

코드를 구성할 때는 M으로 나눌 때 나머지 값이 각각 몇개씩 가지고 있는지를 계산해두면 된다.

※ 총 정리

1. 합 배열에서 나머지가 0인 것의 개수(n1)를 구한다.

2-1. 합 배열에서 나머지가 0인 것들 중에 2개를 선택해서 i의 값이 큰 것에서 작은 것을 빼면 그 사이의 구간이 남으므로 개수(n2)를 nC2의 공식을 사용하여 구한다.

2-2. 합 배열에서 나머지가 같은 것들 중에 2개를 선택하여 nC2공식을 사용하여 개수(n3)을 구한다.

 

2-1 과 2-2는 한꺼번에 식을 구성한다.

 

---

※ 파이썬 코드 정리

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):
    remainder = S[i] % m #합 배열의 모든 값에 나머지 연산 수행
    if remainder == 0: 
        answer += 1
    C[remainder] += 1 #나머지가 같은 인덱스의 개수 값 증가시키기

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

print(answer)