[백준/구간 합] 10986 나머지 합 구하기 풀이 (JAVA)

문제 주소

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

유형

구간 합

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
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());

        int[] arr = new int[n + 1];
        long[] s = new long[n + 1];
        HashMap<Long, Integer> map = new HashMap<>();
        st = new StringTokenizer(br.readLine(), " ");

        HashSet<Long> set = new HashSet<>();
        for (int i = 1; st.hasMoreTokens(); i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            s[i] = (s[i - 1] + arr[i]) % m;

            map.put(s[i], map.getOrDefault(s[i], 0) + 1);
        }

        long answer = 0;
        for (long key : map.keySet()) {
            int num = map.get(key);
            answer += ((long) num * (num - 1) / 2);
        }

        System.out.println(answer + map.getOrDefault(0L, 0));
    }
}

느낀점

• 구간합 몇 문제를 풀어보고 어느정도 감은 왔다고 생각했는데, 해당 문제를 풀고 이렇게까지 응용할 수 있구나라고 생각했다. 구간합은 뭔가 수학적인 지식이랑 엮어서 내기가 좋은 것 같다.

풀이 방법

• 연속된 부분의 구간의 합이 M으로 나누어 떨어진다는건, 모든 배열을 M으로 나눈 나머지로 바꾼뒤에 구간의 합을 더하고, M으로 나눌 때 떨어진다는 것이랑 똑같다.
• 이를 이용해서 S[i] = (S[i-1] + arr[i]) % M 의 구간 합 공식을 구하고 진행했다.
• 먼저 S[i]의 값이 같은 인덱스의 갯수를 구해주면 된다. 예를 들어, S[1] = 3, S[3] = 3 이면, 구간 2부터 3까지의 구간 합이 M으로 나누어 떨어진다는 사실을 알 수 있다.
• 만약에 구간 합이 0인 인덱스가 있으면 인덱스 0부터 시작해서 더하고 나눴을 때 딱 떨어진다는 거니까 먼저 더해줘야한다.
• 그 후, 각 인덱스 갯수에서 2를 뽑는 조합을 구한다음 더해서 해당 답을 도출해내면 된다.
• nC2는 n * (n-1) / 2와 같다.

새로 알게 된 사실

• nC2는 n * (n-1) / 2 인 것을 알았다. (원래 조합 공식은 (n! / (n-r)! r!) 이다.)
• 구간 합의 나머지는 각 요소의 나머지를 더한 다음에 나머지를 한 것이랑 같다는 것을 알았다.
  • (A+B) % C = ((A % C) + (B % C)) % C
• 구간 합은 수학적인 요소랑 엮어서 많이 출제된다는 것을 알았다.