배열과 리스트: 나머지 합 구하기 (백준 10986)

 

10986번: 나머지 합

 

 

 

난이도: 골드 3

풀이: 먼저 배열을 구한 뒤, 합 배열을 구해 놓는다. 수의 합별로 M으로 나누어 떨어지는 값의 개수들을 찾는 것이므로, 합배열을 각각 M으로 나눈 나머지의 배열을 구하고, 0이 되는 값들의 개수를 더하고, 각 나머지의 숫자들별로 nC2를 계산해 구하면 되는 문제이다.

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Q10986 {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int N            = scanner.nextInt();
        int M            = scanner.nextInt();
        long S[]    = new long[N];
        long C[]    = new long[M];
        long answer    = 0;
        S[0]            = scanner.nextInt();
        
        for (int i=1; i < N; i++) {
            S[i] = S[i - 1] + scanner.nextInt();
        }
        
        for (int i = 0; i < N; i++) {
            int remainder    = (int) (S[i] % M);
            if (remainder == 0) answer ++;
            C[remainder] ++;
        }
        
        for (int i = 0; i < M; i++) {
            if (C[i] > 1) {
                answer = answer + (C[i] * (C[i] - 1) / 2);
            }
        }
        
        System.out.println(answer);    
    }
}