나머지 합
Prob
수 N개로 구성된 A집합에서 연속된 구간 합이 M으로 나누어 떨어지는 갯수
Solv
- 모든 경우의 수
시간 초과0 0 1 0 1 2 0 1 2 3 0 1 2 3 4 1 1 2 1 2 3 1 2 3 4 2 2 3 2 3 4 3 3 4 4 - 부분 합
시간 초과0 1 2 3 4 0+1 1+2 2+3 3+4 0+1+2 1+2+3 2+3+4 0+1+2+3 1+2+3+4 0+1+2+3+4 - 누적 합 + 조합
Check
N=5 M=3
A=[1 2 3 1 2]
누적 합
A=[1 3 6 7 9]
누적 합을 M으로 나눈 나머지 A=[0 0 1 1 0]
여기서 나머지가 0인 것 카운트
3
나머지가 같은 것끼리 빼면 나머지가 0인 된다는 것을 이용해 조합 사용
나머지 갯수를 담은 크기가 M인 R
R=[3 2 0]
3C2 + 2C2 = 3 + 1 = 4
