백준[자바]_10986_나머지합_구간합

오늘은 누적합 카테고리 중에서 네번째 골드 문제를 풀었다. 이전에 구간합에 대한 개념을 정리하고 동적계획법을 풀면서 모듈러연산의 분배법칙을 익혀두었더니 다른 골드문제에 비해 쉽게 풀렸던 것 같다. 

[ 문제풀이 & 접근 ]

1. 시간 초과가 나지 않기 위해서는 구간합을 구해야 하는데, 1차원 배열의 경우 dp[k]를 0~k까지의 구간합이라 하고, i<=j 일때,  i+1부터 j까지의 구간합은 dp[j]-dp[i]으로 정의된다. 
2. 모든 구간에 대해서 나머지가 0인 것을 구해야 하기 때문에 (dp[j]-dp[i])%m = 0인 경우의 수를 찾아주어야 한다.
3. 분배법칙에 의해서 dp[j]%m - dp[i]%m=0으로 바꾸어 해석할 수 있다. 
4. 위의 식을 정리하면 다음과 같은 식을 최종적으로 도출할 수 있다. dp[j]%m  = dp[i]%m
5. 구간합을 구하는 식을 적용해 해석해보면, "0부터 시작한 구간합을 m으로 나눈 나머지가 같은 두 수(i, j)를 순서없이 고르자."
   1. 주의 : 일단 누적합을 구하고 m으로 나누면 나머지는 어차피 똑같지 않나 생각할 수 있지만, 수의 크기가 크기 때문에 int형이 감당할 수 없는 크기가 되어 ArrayIndexOutOfBounds가 발생할 여지가 있으니 모듈러의 연산을 사용하거나 배열을 long형으로 선언해야 한다. 
   2. (정정) 직접 시도해보니 long형으로 선언해도 안된다.. 모듈러 연산을 사용해 sum에는 구간합이 아닌 각 구간합의 나머지 개수를 구해야 한다.
6. n개의 수를 순서없이 2개 고르는 경우의 수는 n*(n-1) / (2*1)이다. 

 

package Main;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class _10986_누적합_나머지합 {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        //구간합 나머지 배열
        int dp[] = new int[m];
        
        st = new StringTokenizer(br.readLine());
        int sum = 0;
         for(int i=0; i<n; i++) {
             sum += Integer.parseInt(st.nextToken())%m;
             dp[sum%m]++;
        }
         
         
         long cnt = dp[0];
         for(int i=0; i<m; i++) {
             int a = dp[i];
             cnt += (long)a*(a-1)/2;
         }
         
         
         System.out.println(cnt);
         /*
             (a-b)%c = ((a%c)-(b%c))%c = 0
             5개의 수중에서 2개의 수를 순서 없이 뽑는 경우의 수는 
             5 * 4
             -----
             2 * 1
         */
    }
 
}