[Java] 10986 나머지 합

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

 

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

 

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        Scanner scanner = new Scanner(System.in);
        
        int arr = scanner.nextInt();
        int Num = scanner.nextInt();
        long[] sumArr = new long[arr];
        long[] sameArr = new long[Num];
        long answer = 0;
        
        sumArr[0] = scanner.nextInt();
        for(int i=1; i<arr; i++){
            sumArr[i] = sumArr[i-1] + scanner.nextInt();
        }
        
        for(int i=0; i<arr; i++){
            int remainder = (int)(sumArr[i] % Num);
            if(remainder == 0)
                answer++;
            sameArr[remainder]++;
        }
        
        for(int i=0; i<Num; i++){
            if(sameArr[i] > 1){
                answer += sameArr[i] * (sameArr[i] - 1) / 2;
            }
        }
        System.out.println(answer);
    }
}

▶ int arr = scanner.nextInt() : 수열의 크기를 사용자로부터 입력받아 arr 변수에 저장함

▶ int Num = scanner.nextInt() : 나누어 떨어져야 하는 수를 사용자로부터 입력받아 Num 변수에 저장함

▶ long[] sumArr = new long[arr] : 합 배열을 arr 크기로 선언 후 sumArr 변수에 저장함

▶ long[] sameArr = new long[Num] : 같은 나머지 값을 가진 인덱스를 카운트하는 배열을 Num 크기로 선언 후 sameArr 변수에 저장함

 

sumArr[0] = scanner.nextInt();
    for(int i=1; i<arr; i++){
        sumArr[i] = sumArr[i-1] + scanner.nextInt();
}

▶ 수열의 합 배열을 생성함

    → 예를 들어, {1, 2, 3, 4, 5}라는 배열이 있을 때 합 배열은 이전 인덱스의 값에서 해당 인덱스의 값을 더한 값이므로 {1, 3, 6, 10, 15}가 됨

 

for(int i=0; i<arr; i++){
    int remainder = (int)(sumArr[i] % Num);
    if(remainder == 0)
        answer++;
    sameArr[remainder]++;
}

▶ 합 배열의 각 인덱스 값 중 Num과 나누었을 때 나머지 값을 reaminder 변수에 저장하고 나머지가 0인 경우 answer의 값을 하나 더하고, 나머지가 0이 아니라면 sameArr[remainder]의 값을 하나 더함

 

for(int i=0; i<Num; i++){
    if(sameArr[i] > 1){
        answer += sameArr[i] * (sameArr[i] - 1) / 2;
    }
}

▶ 나누어 떨어져야 하는 수만큼 반복문을 돌리며 sameArr의 인덱스 값이 1 이상인 경우는 answer + (sameArr[i] * (sameArr[i] - 1) / 2)를 계산 후 answer 변수에 저장함

    → 같은 나머지 값을 가지는 인덱스의 조합을 계산하기 위해 (sameArr[i] * (sameArr[i] - 1) / 2)를 계산하고 나머지가 0인 개수를 더한 answer의 값을 더해 출력함