[백준] 10986 나머지 합 (누적 합) - Java

 

10986번: 나머지 합

 

문제 상황

 

 

접근법

• 누적 합 배열 sum 생성
• sum의 모든 값을 M으로 나눈 나머지를 구함
  • 나머지가 0이면 순서쌍의 개수 +1
  • 나머지 값이 같은 원소 중 2개의 원소를 뽑는 모든 경우의 수를 구해 순서쌍의 개수에 더함 (조합)

 

문제 풀이

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());

        st = new StringTokenizer(br.readLine());

        long[] sum = new long[N];
        long[] combi = new long[M];
        long answer = 0;

        sum[0] = Integer.parseInt(st.nextToken());
        for (int i = 1; i < N; i++) {
            sum[i] = sum[i-1] + Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N; i++) {
            int remainder = (int) (sum[i] % M);
            if(remainder == 0) answer++;
            combi[remainder]++;
        }

        for (int i = 0; i < M; i++) {
            if(combi[i] > 1){
                answer += (combi[i] * (combi[i] -1) / 2);
            }
        }

        System.out.println(answer);
    }
}