백준(baekjoon) 10986번: 나머지 합(골드 3, 파이썬 PYTHON) - 누적 합

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

 

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

import sys

N,M=map(int,sys.stdin.readline().split())
A_list=list(map(int,sys.stdin.readline().split()))
A_list.insert(0,0)
remain=[0]*M

for x in range(N):
  A_list[x+1]=A_list[x]+A_list[x+1]
  remain[A_list[x+1]%M]+=1

answer=remain[0]

for x in remain:
  if(x!=0):
    answer+=int(x*(x-1)/2)

print(answer)

 

※ 누적 합

 

 

● 먼저 N과 M을 입력받은 뒤, 뒤에 들어오는 N개의 수를 배열로 만들어 A_list에 저장한다. 그 후 A_list의 맨 앞에 0을 하나 집어넣고, 인덱스 범위가 0부터 M-1 까지이고 값이 0으로 초기화 되어있는 remain 배열을 만들어준다.

 

● x는 0부터 N-1 까지 돌며, 각 단계에서 A_list[x+1] 을 A_list[x]+A_list[x+1] 값으로 갱신해준다. 입력받은 N개의 수를 1번째부터 N번째 까지 수라 하면, 각 단계에서 A_list[x+1]에는 x+1 번째 까지 수의 누적합이 저장되게 된다. 그리고 A_list[x+1] 을 M으로 나눈 값을 인덱스로 하는 remain 요소의 값을 1 더해준다.

 

● remain 배열의 i인덱스 요소는 각 단계에서의 누적합을 M으로 나누었을 때 나머지가 i가 나오는 경우의 횟수를 뜻한다. 누적합의 나머지가 같은 것들 중 두개를 조합하여 빼면 그 사이 숫자들의 합은 M으로 나누어 떨어지게 되므로 remain 배열의 요소 값이 0이 아니라면 for문을 돌며 각 remain 요소 값을 x에 넣어 answer에 int(x*(x-1)/2) 값을 더해준다(이 때 누적합의 나머지가 0이였다면 이는 하나만 골라도 조건에 충족하므로 answer의 초기값에 remain[0]을 넣어준다).

 

● answer 값을 출력해주면 답을 구할 수 있다.