144. 10986(나머지 합) - 자바

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp1 = br.readLine().split(" ");

		int N = Integer.parseInt(tmp1[0]);
		int M = Integer.parseInt(tmp1[1]);
		int sum = 0;
		int[] numSum = new int[M];

		String[] tmp2 = br.readLine().split(" ");
		
		for (int i = 0; i < N; i++) {
			sum = (sum + Integer.parseInt(tmp2[i])) % M;
			numSum[sum]++;
			// 어차피 최종 값만 쓰므로 주소로 증가시켜도 됨
		}

		long result = numSum[0];

		for (int val : numSum) {
			result += (long) val * (val - 1) / 2;
		}
		
		System.out.println(result);
	}
}

문제요약

다양한 구간의 합에서 M으로 나누어 떨어지는 곳을 구하라.

설명

우선 문제에서 출력이 어떻게 나오는지 알아보자.

먼저 백준의 입력 예시로 알아보면,

이 입력으로 각 인덱스별 시작 구간 합을 아래와 같다.

M으로 나눠지는 누적합이 총 7개다.

이런식으로 진행이 되는 것이다.

 

하지만, 큰 수가 들어왔을 때 시간초과없이 i,j구간의 누적합을 위와같이 구하기란 어렵다.

바로 이때 누적합을 사용한다.

다시 보면 누적합 과정에서 M으로 나누어 떨어지는 (나머지가 0) 수는 3,6,9 총 3개이다.

누적합에서 1과 7은 나머지가 1인 수이다.

 

여기서

나머지가 1인 두 구간을 뽑아서 빼준다면? 나머지가 0이 될것이다. (나머지 1인 구간 - 나머지 1인 구간 = 나머지 0인 구간)

즉, 한번의 누적합을 구할 때 나머지를 따로 뽑아서 저장해두고 각 나머지 인덱스에서 2개의 수를 뽑아주면 나머지가 0인 구간을 구할 수 있다.

 

		int N = Integer.parseInt(tmp1[0]);
		int M = Integer.parseInt(tmp1[1]);
		int sum = 0;
		int[] numSum = new int[M];

 

누적합의 나머지를 저장할 배열을 선언해주었다.

index가 M인 이유는 M으로 나눈 나머자의 값이 M을 넘을 수 없기 때문이다.

 

		String[] tmp2 = br.readLine().split(" ");
		
		for (int i = 0; i < N; i++) {
			sum = (sum + Integer.parseInt(tmp2[i])) % M;
			numSum[sum]++;
			// 어차피 최종 값만 쓰므로 주소로 증가시켜도 됨
		}

수가 크면 sum은 int, long 형식으로 표현이 불가능하다.

어차피 누적합의 나머지만 궁금한 것이기 때문에 누적합을 구할때 % 을 사용해서 수의 크기를 줄여 주자.

 

long result = numSum[0];

첫 결과에 나머지가 0인 값을 집어 넣는 이유는 나머지가 0인 값들은 2개의 수를 뽑지 않아도 0으로 나누어 떨어지는 구간이기 때문이다.

 

위의 입력으로 설명하면,

누적합 3,6,9 구간은 2개를 뽑지 않아도 0으로 나누어 떨어진다.

 

값이 int를 넘을 수 있기 때문에 long을 사용한다.

 

for i in numRemainder:
  result += i*(i-1)//2

이제 나머지가 같은 구간 두개를 뽑는다.

위 식은 조합을 표현한다.