[백준 10986] 나머지 합(java)-누적 합

문제보러가기

10986번: 나머지 합

이 문제는 누적 합을 응용해 나머지가 0 인 구간의 개수를 구하는 문제이다.

어떻게 풀어야 하나 해서 검색도 하고 고민.. 항상 느끼지만 기본적인 수학 지식이 있으면 좋을 거 같다 ㅎ..

 

누적 합 이란

 

A [0] + A [1] +... A [i]+..+A [j]+...+A [n]의 숫자에서 A [i]부터 A [j]까지의 합을 구하는걸 미리 합 해놓은 S [] 배열로 구하는 문제이다. -> i~j까지의 합 = s [j]-s [i-1];

 

 

 

 

문제풀이

 

수식이 나오게 된 과정

즉, 누적 합의 나머지가 같은 i, j끼리 조합하여 구간을 만들면 그것이 답의 개수가 된다!

 

만약 s [1]% m==0 && s [3]% m==0 이면 구간 1~3까지가 하나의 답이 되고,

s [2]% m==1 && s [5]% m==1 이면 구간 2~5까지가 또 다른 답이 되는 것이다.

 

 

 

1.누적 합의 나머지가 같은 것의 개수를 센다2. 그 개수로 조합을 만든다 -> 1-3 3-1구간이 같으므로 순서 x 이므로3. 조합은 중복의 경우가 안되므로 s [i] 자체로 나머지가 0이면, 즉 s [i]% m==0이면 바로 답++해준다.

 

 

※ 조합식

n개중에 r개를 뽑는 조합 

                                                  nCr = nPr/r! = n!/(r!(n-r)!)

 

 

#참고로 알고리즘의 크기를 잡을 때 항상 최대 값을 고려하자 ㅎ 

 

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		//누적합 나머지 합
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		long ans = 0;
		long[] mod = new long[(int)m];
		long[] sumArr = new long[n+1];
		st = new StringTokenizer(br.readLine());
		
		for(int i=1;i<=n;i++) {
			long num = Long.parseLong(st.nextToken());
			//i인덱스까지의 누적합을 구해서 저장
			sumArr[i]=sumArr[i-1]+num;
            //누적합의 나머지가 0이라면 바로 답++
			if(sumArr[i]%m==0) ans++;
			//같은 나머지끼리 몇개인지 저장
			mod[(int) (sumArr[i]%m)]+=1;
			
		}
        //같은 나머지 개수로 조합을 구하여 답에 추가한다
		for(int i=0;i<m;i++) {
			ans += mod[i]*(mod[i]-1)/2;
		}
		
		
		System.out.println(ans);
	}

}