Search

BOJ 10986 나머지 합

태그
수학
누적 합

문제 설명

•
NN개의 수가 주어졌을 때, 연속된 부분 구간의 합이 MM으로 나누어 떨어지는 구간의 개수를 구하는 문제

예제 입력/출력

•
입력1
5 3 1 2 3 1 2
Plain Text
복사
•
출력1
7
Plain Text
복사

제약 조건

•
1≤N≤1061 ≤ N ≤ 10^6
•
2≤M≤1032 ≤ M ≤ 10^3
•
0≤Ai≤1090 ≤ A_i ≤ 10^9

문제 풀이

•
접근 누적합 + 나머지 활용 - O(N)O(N)
index
값 A[i]A[i]
누적 합 SkS_k​
Sk mod  3S_k \ mod  3
나머지 개수
1
1
1
1
{0:0, 1:1}
2
2
3
0
{0:1, 1:1}
3
3
6
0
{0:2, 1:1}
4
1
7
1
{0:2, 1:2}
5
2
9
0
{0:3, 1:2}
1.
누적 합 SkS_k 정의
•
SkS_k는 1부터 k까지의 부분합
◦
Sk=A1+A2+…+AkS_k = A_1 + A_2 + … + A_k
•
우리는 다음 조건을 만족하는 구간 (i,j)(i, j)를 찾고자 한다.
◦
Sj−Si−1≡0 (mod M)S_j - S_{i-1} ≡0 (mod M)
2.
나머지 개수 세기
•
모든 SkS_k에 대해 나머지 값의 개수를 미리 카운트 해두면, 원하는 구간 개수를 빠르게 찾을 수 있다.
◦
ex) 나머지 1인 구간 - 나머지 1인 구간 = 나머지 0인 구간
•
누적 합을 계산하면서 MM으로 나눈 나머지를 구한다.
◦
ex) 나머지 0인 경우: 3개, 나머지 1인 경우: 2개
3.
조합 공식 적용
•
누적 합 배열에서 원소 값이 0인 개수만 세어 정답에 더한다.
◦
누적 합 배열의 원소 값이 0이라는 뜻은 원본 리스트의 1부터 k까지의 구간 합이 이미 MM으로 나누어떨어진다는 뜻이기 때문이다.
◦
경우의 수 = +3
•
나머지가 같은 SjS_j와 SiS_i가 CC개 존재하면, 해당 조합으로 만들 수 있는 구간의 개수는 다음과 같다.
◦
C×(C−1)2\frac{C \times (C - 1)}{2}
◦
3C2=3_3C_2 = 3 → 경우의 수 = +3
◦
2C2=1_2C_2 = 1 → 경우의 수 = +1
•
총 경우의 수 = 3 + 3 + 1 = 7

풀이 코드

import sys input = lambda: sys.stdin.readline() # 입력 값 받기 N, M = map(int, input().split()) arr = [0] + list(map(int, input().split())) # 누적합 + 나머지 연산 sum = 0 dp_remainder = [0] * M for i in range(1, N + 1): sum += arr[i] dp_remainder[sum % M] += 1 # 가능한 조합(Combinations) 구하기 ans = dp_remainder[0] # 누적 합 배열에서 원소 값이 0인 개수 세기 for i in dp_remainder: # 원소 값이 같은 2개의 원소를 뽑는 모든 경우의 수 계산 ans += i * (i - 1) // 2 print(ans)
SQL
복사

참고 자료