005 : 나머지 합 구하기

 

 

 

 

 

S[0]을 먼저 TP[0]으로 넣어두고 1부터 시작해도 됨

 

 

 

 

 

 

 

 

 

 

0부터 1 

0부터 2

... 0부터 V-1까지 구간만 우선 생각한다

 

또한 나머지가 있다면 나머지가 같은 것으로 bundling한다

 

*나머지가 0일때도 더해줘야함

 

 

 

나머지는 T와 다르다. 1 ~ T-1 구간에 존재

 

동일한 나머지 bundling이 있다면 조합으로(큰오른쪽, 작은오른쪽 자동으로 순서가 정해지므로) 수를 counter에 더한다

 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        // ISC
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int T = sc.nextInt();

        // D2F
        int[] S = new int[V];
        int[] C = new int[T];
        int plate = 0;
        S[0] = sc.nextInt();
        for (int i = 1; i < V; i++) {
            S[i] = S[i-1] + sc.nextInt();
        }

        // O1
        for (int i = 0; i < V; i++) {
            int R = (S[i] % T);
            if (R == 0)
                plate++;
            C[R]++;
        }

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

        System.out.println(plate);
    }
}