(Python/🥇3)백준알고리즘 10986번 : 나머지 합

 

문제 바로가기 

백준 알고리즘 나머지 합

문제:

 

수 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)

출력:

 

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

 

풀이 :

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

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

sum = 0
div = [0] * M

for i in range(N):
    sum += num[i]
    div[sum % M] += 1

result = div[0]

for i in div:
    result += i*(i-1)//2
print(result)

 

 

처음에는 부분합을 모두 저장하려 했지만 N이 10의 6승이다.시간초과 무조건 난다고 판단했다.

 

부분합을 3으로 나눈 값들을 저장을 해 두었다.

 

div = [3,2,0] 이렇게 들어가게 되는데

부분합이 = 1, 3, 6, 7, 9  이렇게 여서 3으로 나눠 떨어지는수는 3개, 나머지 1이 2개 이다.

같은 나머지를 가진 것끼리 빼주면 0 이 되어 나누어 떨어지게 된다.

 

예를들면 7까지의 7과 1을 빼주면 6으로 나누어 떨어지는것이다.

div[0] 을 넣어주는 이유는 0 부터 그 숫자까지는 안 나누어 떨어진다. 1+2 , 1+2+3 ,, 이 숫자들 처럼

 

그리고 div를 포문을 돌려

조합 함수를 사용하면된다. N개중 2개를 뽑을 확률을 식으로 표현하면 된다.