[JAVA] 백준 10986 나머지 합

 

10986번: 나머지 합 (acmicpc.net)

10986번: 나머지 합

 

- 수 N개 A1, A2,...,An이 주어진다.

- 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램

- Ai+ .... + Aj의 합이 M으로 나누어 떨어지는 (i,j) 쌍의 개수를 구해야 한다. 

 

문제 풀이 

[Java / 백준 10986] 나머지 합 (velog.io)

[Java / 백준 10986] 나머지 합

 

- 모듈러 연산에 의해 

(prefixSum[j] - prefixSum[i])  %MOD = 0을 만족한다면 prefixSum[j]%MOD = prefixSum[i]%MOD도 만족하게 된다. 

index	0	1	2	3	4
value	1	2	3	1	2

 

- 누적합 배열에 저장

index	0	1	2	3	4	5
prefixSum	0	1	3	6	7	9

 

- 모듈러 연산 적용

index	0	1	2	3	4	5
prefixSum % MOD	0	1	0	0	1	0

 

 

 

- 같은 나머지를 가진 누적합 중 2개를 순서없이 뽑는 경우의 수를 세면 됨 

 

0 : 3C2 = 3

1 : 2C2 = 1

 

- 나머지를 담은 배열에서의 0들은 부분 구간이 아닌 첫 인덱스로부터 더한 것이므로 따로 카운트 

 

3+1+3 = 7

 

- 0번째 수부터 n-1번째 수 까지 누적합 sum을 구해가며 그 떄의 나머지를 계산해 remainder[prefixSum%M]++을 해줌

 

 

정답 

 

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

public class Main 
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st ;
        st= new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        long result = 0;
        long remainder[] = new long[n+1];
        long cnt[] = new long[m];
        
        
        
        st = new StringTokenizer(br.readLine());
        
        //누적합을 m으로 나눈 나머지를 배열 S에 저장 
        for(int i=1; i<n+1; i++)
        {
        	remainder[i] = (remainder[i-1] +Integer.parseInt(st.nextToken()))%m;
        	
        	if(remainder[i] ==0)
        	{
        		result++;
        	}
        	
        	//나머지가 같은 인덱스의 수 카운팅
        	cnt[(int)remainder[i]]++;
        }
        
        for(int i=0; i<m; i++)
        {
        	if(cnt[i]>1)
        	{
        		result += (cnt[i]*(cnt[i]-1)/2);
        	}
        }
        
        bw.write(result+"");
        
        bw.flush();
        bw.close();
    }
}