[Java] BJ.10986 나머지 합

 

10986번: 나머지 합

풀이 (구간 합)

문제를 보자마자 풀이가 바로 떠올랐는데 골드 3이라는 난이도와 입력값들의 범위가 맘에 걸리긴 했지만 생각난 풀이로 풀어보기로 했다. 구간합 배열하나를 만든 후 i, j 범위 사이의 모든 구간합들의 차이를 구해서 그 값이 3이면 cnt를 늘리는 식으로 했는데 역시나 시간초과가 났다.

 

먼저 나눠져야 하는 M을 범위로 하는 배열에 구간합을 M으로 나눈 값의 개수를 담는다. 이때, 나머지가 0이면 나누어 떨어지는 구간이므로 개수를 증가시킨다. 그다음 나머지 값이 같은 배열 구간에서 두 구간을 뽑는 모든 경우의 수를 구하면 된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        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());

        long[] S = new long[N+1];
        long[] C = new long[M];

        long ans = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            S[i] = Integer.parseInt(st.nextToken()) + S[i-1];
        }

        for (int i = 1; i <= N; i++) {
            int idx = (int) S[i] % 3;

            if (idx == 0) ans++;

            C[idx]++;
        }

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

        System.out.println(ans);
    }
}