[JAVA/백준] 10986번 : 나머지 합

[문제]

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

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

 

 

<Input>

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

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

 

<Output>

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

 

 

<examples>

-입력

5 3
1 2 3 1 2

 

-출력

7

 

 

 

[풀이]

package Baekjoon;
import java.util.Scanner;

public class P10986_나머지합 {
    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++; //나누어떨어지면 카운트
            C[remainder]++; //바구니에 하나씩 담기
        }

        for(int i =0;i<M;i++){
            if(C[i]>1){
                //나머지 같은 인덱스 중 2개 뽑는 경우의 수를 더하기(2개 뽑는다 = 쌍을 뽑는다.)
                //나머지가 같은 애들끼린 구간합 구하면 M으로 나누어 떨어지는 규칙이 있음
                answer += (C[i] * (C[i]-1)/2);
            }
        }
        System.out.println(answer);
    }

}

 

 

---

 

합 배열을 이용한 문제이다.

경우의 수를 구해야 하기 때문에 

먼저 조건인 M으로 나누어떨어지는 지를 먼저 확인하고 카운트,

그리고 2개 씩 더했을 때 M으로 나누어 떨어지는지를 확인해야 하는데,

M으로 나누었을 때 나머지가 같은 애들이 있는데, 걔네끼리 더하면 M으로 나누어 떨어지는 규칙이 있으므로

(구간합의 시작과 끝이 M으로 나눴을 때 나머지가 같으면 걔네끼리 구간합 더하고 +1해도 M으로 나누어 떨어진다.)

=> 해당 규칙을 적용해 코드를 짜준다.

C배열에 같은 애들끼리 모아서 담아놓았기 때문에 for문을 돌며 조회하며

몇 개가 담겼든, 경우의 수를 구해 카운트해준다.

참고로 조합의 공식은 다음과 같다.

 

Case 0 :  3일 경우, 경우의 수는 3C2 = 3*2*1 / 2*1 = 3 이고 

Case 1 :  2일 경우, 경우의 수는 2C2 = 2*1 / 2*1 = 1 임

 

여튼 조합식을 이용해 카운트해주면 

최종 결과를 구할 수 있다.