[BJ]G3 10986. 나머지 합

BJ G3 10986 나머지 합

 

 

문제링크

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/siBSDIbXZCU

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l3;

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

/**
 * @author 은서파
 * @since 2022. 8. 3.
 * @see https://www.acmicpc.net/problem/10986
 * @git https://github.com/quietjun/algo_aps/blob/master/src/main/java/bj/gold/l3/BJ_G3_10986_나머지합.java
 * @youtube
 * @performance 161192 464
 * @category #누적합
 * @note 기본적인 누적합에 %응용 추가
 */

public class BJ_G3_10986_나머지합 {

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;
    static int N, M;
    static int[] modCnt;
    static int A;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        M = Integer.parseInt(tokens.nextToken());

        modCnt = new int[M]; // 우리가 필요한 것은 나머지의 개수!!
        tokens = new StringTokenizer(input.readLine());
        int sum = 0;
        for (int n = 0; n < N; n++) {
            sum = (sum + Integer.parseInt(tokens.nextToken())) % M;
            modCnt[sum]++;
        }

        long cnt = modCnt[0];
        for (int i = 0; i < modCnt.length; i++) {
            // 형변환 주의
            cnt += (long) modCnt[i] * (modCnt[i] - 1) / 2; // 조합 과정에서 나온 결과
        }
        //System.out.println(Arrays.toString(modCnt));
        System.out.println(cnt);
    }

    // REMOVE_START
    private static String src = "5 3\n"
                                + "1 2 3 1 2";
    // REMOVE_END

}