배열의 구간 합 3 - 나머지 합 구하기

https://www.acmicpc.net/problem/10986

220928

10986번: 나머지 합

package day1.bj_10986;

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        long[] S = new long[N]; //합 배열
        long[] C = new long[M]; // 나머지 같은 애들 계수용

        long answer = 0;

        //합배열 정의
        S[0] = sc.nextInt();
        for(int i=1;i<N;i++){
            S[i] = S[i-1]+sc.nextInt();
        }

        for(int i=0;i<N;i++){
            int remainder = (int)(S[i]%M); //나머지
            if(remainder==0) answer++;//0~i구간이 정답 구간 중 하나임
            C[remainder]++;//동일 나머지를 갖는 구간 구하기 위함
        }


        for(int i=0;i<M;i++){
            if(C[i]>1){//동일 나머지를 갖는 원소 2개 이상인 부분에서 nC2조합 갈김
                answer += C[i]*(C[i]-1)/2;
            }

        }
        System.out.println(answer);




    }


}