[백준] 10986 나머지 합- 누적합(Prefix Sum) + 수학(나머지) JAVA

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

10986번: 나머지 합

코드설명

누적합과 수학(나머지) 문제입니다.

 

문제조건을 보면, O(N^2)를 활용하여 진행할시 시간초과가 발생합니다.

 

수학(나머지)를 활용하여 진행합니다.

( (prefixSum[j] - prefixSum[i] ) % M == 0) 인값을 구하는것이 목표입니다.

위의 식을 전개할시

( (prefixSum[j] % M) - prefixSum[i] % M ) == 0)

prefixSum[j] % M == prefixSum[i] % M 일 경우, i ~ j 구간합이 M으로 나눌경우 0 이라는 것을 알 수 있습니다.

 

즉, 나머지값이 같은 구간합의 개수 중 2개를 뽑아서 각각 다 더하면 된다는 것입니다.

나머지(prefixSumRemian[1])가 1일경우의 구간합의 개수를 모두 구하고,

나머지(prefixSumRemian[2])가 2일경우의 구간합의 개수를 모두 구하고,

...

..

 

한뒤, prefixSumRemian[1]에서 2가지를 구해주는 nCr 공식을 통하여서 값을 구해줍니다.

nCr = (n!) / r!(n-r!) 에 의하여

nC2 일경우 (n) * (n-1) / 2 입니다.

 

코드

prefixSum 배열없이 바로 함수로 처리한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M;
	public static long[] prefixSum;
	public static long[] prefixSumRemian;
	public static long answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
 
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	prefixSum = new long[N+1];
    	prefixSumRemian = new long[M];
    	
    	long sumValue = 0;
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		sumValue += Integer.parseInt(st.nextToken());
    		int remainder = (int) (sumValue % M);
    		prefixSumRemian[remainder] += 1; //나머지 개수를 세서 1씩 증가시킵니다.
    	}
    	
    	answer += prefixSumRemian[0];
    	for(int i=0;i<M;i++) {
    		answer += prefixSumRemian[i] * (prefixSumRemian[i] - 1) / 2; // N*(N-1) / 2
    	}
    
    	System.out.println(answer);
    }
    
    
}

 

prefixSum 배열로 prefixSum[1 ~ N]를 통해 처리한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M;
	public static int[] arr;
	public static long[] prefixSum;
	public static long[] prefixSumRemian;
	public static long answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
 
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	prefixSum = new long[N+1];
    	prefixSumRemian = new long[M];
    	
    	long sumValue = 0;
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		sumValue += Integer.parseInt(st.nextToken());
    		prefixSum[i+1] = sumValue;
    	}
    	
    	for(int i=1;i<=N;i++) {
    		int remainder = (int) (prefixSum[i] % M);
    		prefixSumRemian[remainder] += 1; //나머지 개수를 세서 1씩 증가시킵니다.
    	}
    	
    	answer += prefixSumRemian[0];
    	for(int i=0;i<M;i++) {
    		answer += prefixSumRemian[i] * (prefixSumRemian[i] - 1) / 2; // N*(N-1) / 2
    	}
    
    	System.out.println(answer);
    }
    
    
}

 

시간초과 ( O(N^2)의 연산이 들어가있습니다. )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M;
	public static int[] arr;
	public static int[] prefixSum;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
 
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	prefixSum = new int[N+1];
    	
    	int sumValue = 0;
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    		sumValue += arr[i];
    		prefixSum[i+1] = sumValue;
    	}
 
    	for(int i=0;i<=N;i++) {
    		for(int j=i+1;j<=N;j++) {
    			sumValue = prefixSum[j] - prefixSum[i];
    			if(sumValue % M == 0) answer += 1;
    		}
    	}
    	
    	System.out.println(answer);
    	
    }
    
    
}