[Java] BOJ10986 나머지 합 구하기

문제

N개의 수 A1, A2...., An이 주어졌을 때 연속된 부분의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그래밍을 작성하시오. 즉, Ai+.... Aj(i<=j)의 합이 M으로 나누어 떻어지는 (i,j)쌍의 개수를 구하시오.
https://www.acmicpc.net/problem/10986

입력

1번째 줄에 N과 M, 2번째 줄에 N개의 수 A1,A2,,,,An이 주어진다.

출력

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

풀이 과정

부분합을 구하면서 입력 받은 M으로 나누어지는 구간의 개수를 구하면 되는 문제이다. 제일 먼저 해야할 일은 index 0부터 length까지의 부분합을 저장하는 배열을 만들고, 각 인덱스마다 M으로 나눈 값으로 갱신해준다. 만약 이때 값이 0(M으로 나누어짐) Answer++시켜준다.
하지만... 인덱스가 0부터 시작된 것이 아니라 중간 부터 시작되는 구간은 어떻게 생각해야하는 것일까??

책을 보면서 이해한 내용은 다음과 같다.
먼저, 배열의 구간합은 Arr[j] - Arr[i]로 표현이 가능하다.(이때 i<=j)
그럼 이 구간들에서 M으로 떨어지는 구간은 도대체 어떻게 구할 수 있는 것 일까..?

Arr[j]%M==N. Arr[i]%M==N 이면 ((Arr[j]-Arr[i])%M==0)
즉 우리가 구간합의 값을 M으로 나눈 값으로 이루어진 배열을 만들었을때, 값이 같은 인덱스들중 두개를 고르면 해당 구간은 M으로 나누어 떨어진다는 것을 의미한다는 것이다.

풀이코드

package 자료구조;

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

public class 나머지합구하기 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        long[] arr = new long[N];//구간합을 저장하는 배열.
        long[] remainder = new long[M];//나머지들의 개수를 저장하는 배열
        //이제 나머지를 구해야 됨. M으로 나누면서 가질수 있는 나머지 M개 0 ~ M-1
        long answer =0;
        st = new StringTokenizer(br.readLine());
        arr[0] = Integer.parseInt(st.nextToken());
        for (int i = 1; i < arr.length; i++) {
            arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken());
        }
        // 0 ~ N까지의 구간합을 구했음.

        for (int i = 0; i < N; i++) {
            int idx = (int)(arr[i]%M);//나머지로 인덱스를 구함
            if(idx == 0) answer++;
            remainder[idx]++;
        }

        for (int i = 0; i < M; i++) {
            if (remainder[i] >= 2) {
                answer+=(remainder[i]*(remainder[i]-1))/2;//조합을 구하는 식.

            }
        }
        System.out.println(answer);


    }
}

결론

확실히 골드 문제이다 보니깐 어려웠던 문제였던 것 같다. 풀때마다 느끼는데, long, int 때문에 틀리는 문제도 꽤 있는 것 같다.. kuku 열심히 해야지