[백준 10986] 나머지합 구하기 (구간 합)

 

📝 문제

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

💡 힌트

S[i] % M의 값과 S[j] % M의 값이 같다면 (S[i]-S[j] ) % M은 0이다.

변경된 합 배열에서 S[i] , S[j]의 값이 같으면 원본 배열에서 i+1부터 j까지의 구간 합이 M으로 나누어떨어지는 구간이다.

💻 코드

package org.kyhslam.DoItAlgorithm.ch02;

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();

        int[] arr = new int[N];
        int[] S = new int[N];
        int[] C = new int[M];

        int answer = 0;

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();

            //합 배열 셋팅
            if (i == 0) {
                S[i] = arr[i];
            } else {
                S[i] = arr[i] + S[i - 1];
            }
        }

        //합 배열 % 연산 수행
        for (int i = 0; i < N; i++) {
            S[i] =  S[i] % M;
            int remainder = S[i] % M;
            if(S[i] == 0) answer++;

            //나머지가 같은 인덱스의 개수를 카운팅
            C[remainder]++;
        }

        for (int i = 0; i < M; i++) {
            if (C[i] > 1) {
                //나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 더하기
                answer = answer + (C[i] * (C[i] - 1) / 2);
            }
        }

        System.out.println("answer = " + answer);
    }

    public static void arrView(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}