[백준] 나머지합 / 누적합

 

 

Glod

 

 

문제

 

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

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

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

 

 

입력

 

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

 

 

출력

 

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

 

 

---

 

풀이

 

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

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[] dp = new int[N+1];
        int[] cnt = new int[M];
        
        // 나머지가 0인 경우는 맨 처음부터 그 위치까지가 M으로 나눠떨어짐을 의미. 
        // 시작에 0도 포함할 수 있도록 미리 1로 셋팅 (나머지가 0인것의 수 조합에서, 시작점이 0인것도 포함할 수 있도록) 
        cnt[0] = 1 ; 
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            int num = Integer.parseInt(st.nextToken());
            dp[i] = (dp[i-1] + num)%M;
            cnt[dp[i]%M] += 1;
        }

        long count = 0;
        for(int i=0; i<M; i++){
           count += ((long)cnt[i]*(cnt[i]-1))/2; 
        }
        
        System.out.println(count);
    }
}

 

 

처음에는 모든 부분수열을 구하는 방법을 사용하였으나, 시간 초과가 발생하게 되었다.

나머지가 같은 구간들이 M으로 나누어떨어지는 구간이 된다는 점을 활용하여 시간초과 문제를 해결할 수 있었다. 

 

 

해결방법

 

• 0부터 i까지의 누적합을 M으로 나눈 나머지를 dp[i]에 저장한다
• 각 나머지가 나온 횟수를 배열 cnt[]에 저장한다.
  -> 이 때 나머지가 0인 경우는 0부터 해당 숫자까지도 포함할 수 있으므로(시작점이 0), 그 경우를 위해 미리 카운트+1 한다.
• 동일한 나머지를 가진 구간이 M으로 나누어 떨어지는 구간이므로, 나머지가 같은 수의 조합을 구해 모두 더한다.
  -> n*(n-1)/2 (n개의 수 중 2개의 숫자를 선택하는 조함)
  -> 2개의 수를 구하는 이유는, 부분수열의 시작점과 끝점을 구하기 위함이다. 

5개 수 중 2개의 숫자를 구하는 공식

n개의 수 중 2개의 숫자를 구하는 공식

 

 

---

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