문제

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

해설

해당 문제는 자료형을 long 타입으로 해야된다.

왜냐하면 주어진 A의 최대 값은 1억인데 최대 10000번 더해지게 된다면 int형의 최대 값인 -21억~21억을 훌쩍 넘겨 ArrayIndexOut 런타임 에러가 출력 될것이다. 그러니 그냥 대부분 long 타입으로 배열, 변수를 선언해라

1. 그림처럼 배열이 주어져 있다면 새로운 배열을 생성하여 누적 합을 저장하는 배열을 생성하자

2. 누적합 배열을 생성했다면 누적합의 각 배열을 입력받은 key값으로 나눠준다.(이때 나누기 연산은 %을 사용한다.)

이떄 저장한 값에서 0이 되는 인덱스 갯수를 세어준다.

또한 각 갯수를 또 다른 배열에 저장해준다. 예를들어 다음 그림처럼 해주면 된다.

이후 컴비네이션을 사용해서 0이 나왔을때 1이 나왔을때 2가 나왔을떄의 갯수를 출력하는 결과값에 더해준다.

나머지가 같은 값끼리(0포함) 구간을 선택하면 해당 구간의 합은 반드시 나누려는 값이랑 나누어 떨어지게 된다. 그러므로 동일한 값중 2개를 선택해야 하므로 동일한 값이 최소 2개 이상은 있어야 된다. 이러한 경우 다음과 같은 코드를 만들 수 있다.

if(cnt[i] >1){ // 2개 이상인 경우
    result += (cnt[i]*(cnt[i]-1))/2; // 컴비네이션 nCm 공식
}

이후 해당 값을 결과값에 출력해준다.

코드

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

public class J10986 {
    public static void main(String[] args) throws IOException{
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
        String[] input = buffer.readLine().split(" ");
        int index = Integer.parseInt(input[0]);
        int key = Integer.parseInt(input[1]);

        long[] array = new long[index];
        long[] cnt = new long[key];
        input = buffer.readLine().split(" ");

        long sum = 0;
        long count = 0;
        long result = 0;

        for(int i = 0; i < index; i++){
            sum += Long.parseLong(input[i]);
            array[i] = sum%key;

            if(array[i] == 0){
                count++;
            }
            
            cnt[(int)array[i]]++;
        }

        result = count;

        for(int i = 0; i < key; i++){
            if(cnt[i] >1){
                result += (cnt[i]*(cnt[i]-1))/2;
            }
        }
        System.out.println(result);
    }
}