백준 10986[자바] java 나머지 합

 

문제 링크: https://www.acmicpc.net/problem/10986

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으로 나누어 떨어지는 구간의 개수를 출력한다.

 

▶해설

 

나머지의 합이 M으로 떨어지는 구간의 개수를 구하는 문제입니다. 그렇다면 M으로 떨어지는 구간 2가지를 선택해야 합니다. 

 

풀이로 고려할 대상은 나머지에 대한 투포인터, 누적합입니다.

 

첫 번째 - 투포인터

 

- 정렬을 한 상태여야 left, right의 증가, 감소를 선택할 수 있으므로 사용할 수 없습니다. 

 

두 번째 - 누적합

 

누적합을 구한 후 해당 구간까지의 나머지를 구할 수 있습니다. 구한 나머지를 활용해야 합니다.

 

구간의 합의 나머지가 0이 되는 조건을 살펴보겠습니다. 

 

1. 현재 누적합 나머지가 0

 

현재 자리까지의 누적 합의 나머지가 0이라면 그대로 개수를 더합니다. i<=j이이므로 자기 자신이 선택되도 됩니다. 

 

2. 두 누적합 나머지를 뺐을 때 0

 

2-1. 두 누적합 모두 0

 

누적합이므로 A구간, B구간까지의 누적합의 나머지가 모두 0이라면 A~B까지는 M의 배수입니다. 그래서 B-A를 했을 때 M의 배수가 남으므로 개수를 더합니다. 

 

1과 2-1의 개수를 더하는 것은 0이 되는 T개의 개수 + 0이 되는 2개를 하나로 묶은 값 따라서 (T(T+1))/2가 됩니다. 

 

result+=((sum[0]*(sum[0]+1))/2);

 

 

2-2. 두 누적합이 0이 아닐 때

 

위에서 본 것처럼 B, A구간을 선택하고 나머지의 합이 0이 됐을 때이므로 같은 나머지를 가지는 개수를 세줍니다. 하지만 위의 경우와 다르게 개개인 하나씩 세는 것이 빠지므로 T개 있을 때 ((T-1)(T))/2의 식을 가지게 됩니다. 

 

for(int i=1; i<m; i++){
    result+=(((sum[i]-1)*(sum[i]))/2);
}

 

3. 배열 만들기

 

위의 풀이를 사용하기 위해선 배열을 만들어줘야 합니다. 0~M-1까지의 나머지를 가지기 때문에 배열의 길이는 M입니다. 이제 누적합을 구하며, 구간의 나머지합을 구해줍니다. 이때 주의할 점은 개수가 10^12까지 갈 수 있기 때문에 전체 카운터인 result와 나머지를 담는 배열은 long으로 해줘야 합니다.

 

sum = new long[m];
int [] arr = new int[n];
arr[0] = Integer.parseInt(s1[0])%m;
sum[arr[0]]++;
long result =0;

for(int i=1; i<n; i++){
    int num = Integer.parseInt(s1[i]);
    arr[i]+=(arr[i-1]+num)%m;
    sum[arr[i]%m]++;
}

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.*;
import java.util.*;


public class Main {

    static int n,m;
    static long []sum;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        String[] s1 = br.readLine().split(" ");

        sum = new long[m];
        int [] arr = new int[n];
        arr[0] = Integer.parseInt(s1[0])%m;
        sum[arr[0]]++;
        long result =0;

        for(int i=1; i<n; i++){
            int num = Integer.parseInt(s1[i]);
            arr[i]+=(arr[i-1]+num)%m;
            sum[arr[i]%m]++;
        }

        result+=((sum[0]*(sum[0]+1))/2);

        for(int i=1; i<m; i++){
            result+=(((sum[i]-1)*(sum[i]))/2);
        }

        System.out.println(result);
    }
}