[ProblemSolving] 백준 - 10986 나머지합 (구간합)
문제 링크
문제 설명
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3)
둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 10^9)
출력
첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.
예제 입력1
5 3
1 2 3 1 2
예제 출력1
7
나의 풀이
연속된 부분 구간 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 문제다.
S(n)은 arr[0], .. arr[n]까지의 누적합일때,
(S(j) - S(i)) % m == 0 인 경우이므로, S(j)% m = S(i) % m
이다. (이때, j > i+1)
다시 말해서, 누적합에서 m으로 나눈 나머지가 같은 것 끼리 짝지으면 그것이 M으로 나누어 떨어지는 구간의 개수가 될 것이다.
mod[x] = y는 나머지가 x인 개수 y의 의미
로, 나머지 temp에 해당 하는 경우 값을 갱신한다.
각 나머지 개수 y에 대한 yC2(조합)을 구해서 개수를 모두 구한다.
코드
n, m = map(int, input().split())
arr = list(map(int, input().split()))
sum_value = 0
cnt = 0
mod = [0]*m
for i in range(len(arr)):
sum_value += arr[i]
temp = sum_value%m
if temp ==0:
cnt += 1
mod[temp] += 1
for i in range(len(mod)):
cnt += mod[i]*(mod[i]-1)//2
print(cnt)
Author And Source
이 문제에 관하여([ProblemSolving] 백준 - 10986 나머지합 (구간합)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@redcarrot01/ProblemSolving-백준-10986-나머지합-구간합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)