[백준] 10986 나머지합

문제보기

S[i] 를 0번째부터 i번째까지 원소의 합이라고 할 때, a번째부터 b번째까지 원소의 합은 S[b] - S[a-1] 로 구할 수 있다. 이렇게하면 구간합 구하는 연산을 O(1)으로 구할 수 있기에 시간복잡도를 줄여주는 효자같은 개념이다!

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


class Main{
	
	static int ip(String s){ return Integer.parseInt(s); };

	
     public static void main(String[] args) throws IOException{
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(br.readLine());

         int n = ip(st.nextToken());
         int m = ip(st.nextToken());
         int[] nums = new int[n]; // 주어진 숫자 배열을 저장할 변수 

         st = new StringTokenizer(br.readLine());
         for(int i = 0 ; i < n ; i++) {
        	 nums[i] = ip(st.nextToken());
         }

         long[] sums = new long[n]; // 이 녀석이 S[i]의 역할을 할 예정 
         int[] r = new int[m]; // 나머지가 i인 부분합은 몇개가 있을지 저장하는 배열 
		// 초항 처리 
         sums[0] = nums[0];
         r[(int)(sums[0]%m)]++;
         
		// 부분합을 쭉 구하면서, 해당 부분합을 m으로 나눈 나머지에 따라 배열 r에 적절히 ++ 해준다 
         for(int i = 1 ; i < n ; i++) {
        	 sums[i] = sums[i-1] + nums[i];
        	 r[(int)(sums[i]%m)]++;
         }
   		

		// 나머지가 같은 부분합은 결국 걔네들끼리 빼주면 나머지가 이쁘게 제거되는것이므로 딱 나누어 떨어질 수 있게 된다. 
         long ans = 0;
         for(int i = 0 ; i < m ; i++ ) {
        	 long s = r[i];
        	 if(s < 2) continue; // 최소 두개는 있어야 nC2가 가능하다 
        	 ans += s*(s-1)/2;
         }
         ans += r[0]; // 나머지가 0인 경우는 그 자체로 나누어 떨어지기 때문 
         System.out.println(ans);
     }
}