백준 10986번(나머지 합)[JAVA]

풀이

수학적으로 규칙을 발견해야 한다!
이 문제에선 특정 구간 수들의 나머지 연산 결과 값을 더한 후 나머지 연산을 한 결과 값과, 그 구간 합의 나머지 연산 결과 값이 동일하다.
그러므로 termSum[i]%m과 termSum[j]%m의 값이 같다면 (termSum[i]-termSum[j])%m은 0이다.(여기서 j~i의 구간은 입력받은 배열에서 j+1~i이다).
즉, 합 배열의 원소를 m으로 나눈 나머지를 기록하고, termSum[i]와 termSum[j]가 같은 (i,j) 쌍을 찾으면, 입력받은 배열에서 j+1부터 i까지의 구간 합이 m으로 나누어 떨어진다는 것이다.
수식으로 나타내면 (A+B)%C = ((A%C) + (B%C))%C 이다.

1. 그러므로 1차원 배열의 구간 합 구하기에서와 같이, 입력 받은 값들의 합 배열을 먼저 구해놓고 접근해야 한다.
2. 그 후, 합 배열의 모든 값을 m으로 나머지 연산을 수행하고 이를 기록한다. 여기서 나머지 연산을 수행한 값이 0이면, 0부터 그 인덱스까지의 구간 합을 m으로 나머지 연산을 수행한 값이 0이라는 뜻이므로, 바로 결과값(result)에 더해준다.
3. 0이 아닌 나머지 값들은, 그 값을 가지고 있는 인덱스의 개수를 센다. 세는 방법은 이항 계수(nCr)를 사용하여 센다. 구간을 정하는 기준이 i,j 이렇게 2가지므로, 나머지가 될 수 있는 값이 n이고, i,j이 2가지가 r이다.

소스 코드

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

public class 나머지합 {
	public static void main(String[] arg) throws Exception {
		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[] termSum = new long[n];
		
        //나머지 결과 값 배열
        long[] remain = new long[m];
		
        //결과
        long result = 0;
        
        //위 설명의 1. 합 배열 초기화
        st = new StringTokenizer(br.readLine());
		termSum[0] = Integer.parseInt(st.nextToken());
		for (int i = 1; i < n; i++) {
			termSum[i] = termSum[i-1] + Integer.parseInt(st.nextToken());
		}

		//위 설명의 2. 합 배열에서 나머지 연산 결과가 같은 인덱스의 개수 세기
		for (int i = 0; i < n; i++) {
			int remainder = (int)(termSum[i]%m);
			//0이면 바로 결과값에 추가
			if (termSum[i] % m == 0) { 
				result++;
			}
			//개수 세기
			remain[remainder]++;			
		}
		
		for (int i = 0; i < m; i++) {
			//나머지 값마다 nCr값을 결과값에 더해주기
			result = result + (remain[i]*(remain[i]-1)/2);
		}
		
		System.out.println(result);
		return;
	}
}

태클 감사합니다.
조언 환영입니다.