[백준 10986] 나머지 합 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/10986

 

문제

수 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으로 나누어 떨어지는 구간의 개수를 출력한다.

풀이

접근법

1. 어떠한 구간에 대해서 M으로 나누어 떨어져야 한다면, 처음 ~ 시작, 처음 ~ 끝에 대한 누적합에 대해서 M으로 나눈 나머지가 같아야 한다. 왜냐하면 겹치는 구간(시작 ~ 끝)에 대해서는 M으로 나눈 나머지가 0이기 때문이다.
2. 개수를 세기 위해서는 각각의 구간에 대해서 2개를 고르면 되니까 조합 공식을 사용해서 ans에 더해주면 된다.

 

코드

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[] prefix = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++) prefix[i] = Integer.parseInt(st.nextToken());
        // 1. 어떠한 구간에 대해서 M으로 나누어 떨어져야 한다면, 
        // 처음 ~ 시작, 처음 ~ 끝에 대한 누적합에 대해서 M으로 나눈 나머지가 같아야 한다. 
        // 왜냐하면 겹치는 구간(시작 ~ 끝)에 대해서는 M으로 나눈 나머지가 0이기 때문이다.
        for(int i=1;i<=N;i++) prefix[i] = (prefix[i] + prefix[i-1])%M;
        int[] count = new int[M];
        for(int i=0;i<=N;i++) count[prefix[i]]++;
        long ans = 0;
        // 2. 개수를 세기 위해서는 각각의 구간에 대해서 2개를 고르면 되니까 
        // 조합 공식을 사용해서 ans에 더해주면 된다.
        for(int i=0;i<M;i++) {
            ans += (long)count[i]*(count[i]-1)/2;
        }
        System.out.println(ans);
    }
}

 

6분 걸렸다 ! 아이디어만 있으면 쉽게 풀 수 있다 !