[백준] 10986번 나머지합

문제 설명

• https://www.acmicpc.net/problem/10986
• Gold 3

문제 풀이

• 구간합 및 수학적 접근으로 풀이
• 문제의 인사이트는 다음과 같다
  - 구간합 S[i]에 대해 (i,j) 구간합이 M으로 나눠지려면
  • (S[j] - S[i-1])%M = 0
  • S[j]%M = S[i-1]%M인 케이스면 해당 구간은 M으로 나눠짐
• 따라서 S[i]의 나머지별로 개수를 카운트 해주는 배열을 유지 (cnt[i] : 나머지가 i인 S의 개수)
• 풀이는 다음과 같다

1. S[i] % M = 0 인 케이스는 우선 둘 선택하지 않아도 만족하니 결과에 더해줌
2. cnt[i]가 2이상인 경우 2개를 고르는 경우의 수를 모두 더해줌 (nC2)

• Gold3이 맞나..

소스 코드 (JAVA)

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

public class Main {

    static int N, M;
    static int[] arr;
    static int[] preSum; // 입력 배열의 구간합
    static long[] cnt;    // 나머지가 i인 수들의 개수

    static void initPreSum() {
        int ps = 0;
        for (int i = 0; i < N; i++) {
            ps = (ps + arr[i]) % M;
            preSum[i] = ps;
            cnt[ps]++;
        }
    }

    static void solve() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        preSum = new int[N];
        cnt = new long[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        initPreSum();
        // 1. 나머지 0인 애들 -> 2개 선택하지 않아도 이미 만족
        long res = cnt[0];
        // 2. 나머지 1이상인 애들 -> 2개 선택하는 경우의 수
        for (int i = 0; i < M; i++) {
            if (cnt[i] > 1) {
                res += (cnt[i] * (cnt[i] - 1) / 2);
            }
        }

        bw.write(res + "\n");
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        solve();
    }
}