백준 10986번 : 나머지 합 [Java]

문제

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

10986번: 나머지 합

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
         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());

         int[] nums = new int[N + 1];
         st = new StringTokenizer(br.readLine());
         for(int i = 1; i <= N; i++){ //배열 입력받기
             nums[i] = Integer.parseInt(st.nextToken());
         }
         //구간합
         int[] sum = new int[N + 1];
         for(int i = 1; i <= N; i++) {
        	 sum[i] = sum[i - 1] + nums[i];
         }
         int result = 0;
         /**
          * sum[j] - sum[i - 1]
          */
         for(int i = 1; i <= N; i++) {
        	for(int j = i; j <= N; j++) {
        		//System.out.println("("+i+", "+j+") : "+(sum[j] - sum[i - 1]));
        		if((sum[j] - sum[i - 1]) % M == 0) {
        			result++;
        		}
        	}
         }
         System.out.println(result);
    }
         
         
}

처음에 그냥 단순히 구간합으로 돌렸더니 시간 초과가 떴다.

일단 원래 배열의 내용을 따로 저장할 필요도 없다는걸 깨달았다.

(A + B) % C = (A % C + B % C) % C라는 것을 이용하면 

특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값 = 이 구간 합의 나머지 연산을 한 값 이다.

S[]가 합을 M으로 나머지 연산을 한 결과일때

S[j] % M == S[i] % M 이라면

(S[j] - S[i]) % M은 0이다. 

즉, S[j]와 S[i]가 같은 쌍을 찾으면 원본 배열에서 i + 1부터 j까지의 구간 합이 M으로 나누어 떨어진다는 것을 알 수 있다.

 

값이 같은 것들의 개수를 저장해두고

조합으로 개수를 계산 한 후 answer에 더한다.

 

그런데 자꾸 런타임에러가 나서 이유를 모르다가 long으로 바꾸니 해결이 됐다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
         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[] sum = new long[N + 1];
         st = new StringTokenizer(br.readLine());
         for(int i = 1; i <= N; i++) {
        	 sum[i] = sum[i - 1] + Integer.parseInt(st.nextToken());
         }
         long answer = 0;

         long[] count = new long[M + 1];
         for(int i = 1; i <= N; i++) {
        	 sum[i] = sum[i] % M;
        	 int remainder = (int) sum[i];
        	 if(remainder == 0) answer++;// (0, i)의 개수 세기
        	 count[remainder]++; //나머지 개수 세기
         }

         for(int i = 0; i < M; i++) {
        	 if(count[i] > 1) {
        		 answer = answer + (count[i] * (count[i] - 1) / 2); //조합 계산
        	 }
         }
         
         System.out.println(answer);
    }
         
         
}