[백준/Java] #10986 나머지 합

📝 나머지 합

사용 언어 : Java
레벨 : 골드 3

 

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

 

🔎 문제 설명

 

✅ 풀이

문제를 읽어봤을 때는 간단한 문제인 것 같았다. 하지만 N의 최댓값은 10^6 개 이고 각 구간의 합들을 구해야 하기 때문에 1초 안에 연산하기는 쉽지 않다. 결국 다른 방법을 써야한다는 것인데 이 문제에는  구간 합 공식을 적용해서 풀면 빠르게 풀 수 있다. 

구간 합에 대해서는 저번에 구간 합 구하기 문제들을 풀었을 때 적어 놓았다.

https://gureumi74.tistory.com/65

[백준/Java] #11659 구간 합 구하기 4, #11660 구간 합 구하기 5

 

일단 입력값들을 구간 합 배열로 만들어주고, 그 구간 합 배열을 모두 m으로 나누어준다. 그럼 구간합 배열 [i] 가 만약 0이라면 0부터 i 까지의 구간 합들은 m으로 나누어 떨어진다는 것을 알 수 있다! 정답값으로 출력할 result 에 0의 개수를 더해주면 0 ~ i 구간 합이 m 으로 나누어떨어지는 개수를 구할 수 있다.

🤔 그렇다면 다른 구간 합들은 어떻게 구할까? 

구간 합 공식에서 S[i ~ j] = S[j] - S[i - 1] 이였던 것을 생각해보자.

이 공식을 바탕으로 만약 S[i] = S[j] 라면 m 으로 나누어떨어지는 구간 합 = S[j] - S[i + 1] 이 될 것이다.  

구간 합 배열 : [1, 0, 0, 1, 0] 일 때
구간 0 ~ 3 을 봐보면 두 구간 합의 값이 1로 동일하다.
구간 0 ~ 3 에서 구간 합이 0 이 되려면 j 값 (1) 을 빼줘야 하는데 i 와 j 값은 동일하니까 구간에 i + 1 로 i 값을 뺴주는 것이다.

 

그럼 결국 같은 값을 가지고 있는 애들 중 2개를 뽑는 경우의 수를 구하고 모두 더하면 m 으로 나눴을 때 구간 합이 0이 되는 구간 합의 개수를 구할 수가 있다. 👏🏻

 

💻 최종 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input =  br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int[] arr = new int[n];
        long[] sumArr = new long[n]; // 합배열
        long[] remainArr = new long[m]; // 나눈 나머지들의 개수 카운팅

        input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(input[i]);

            if (i == 0) {
                sumArr[i] = arr[i];
            } else {
                sumArr[i] = sumArr[i - 1] + arr[i];
            }
        }

        // 합배열 m 으로 나눈 나머지로 변경, 나머지값 카운팅
        for (int i = 0; i < n; i++) {
            sumArr[i] %= m;
            remainArr[(int) sumArr[i]]++;
        }

        long result = remainArr[0]; // m으로 나누어떨어지는 구간합 개수를 먼저 넣어줌

        for (int i = 0; i < m; i++) {
            // 카운팅 된 나머지값들 중 2개를 고르는 경우의 수 고르기
            if (remainArr[i] > 1) {
                result += remainArr[i] * (remainArr[i] - 1) / 2;
            }
        }

        bw.write(String.valueOf(result));
        bw.close();
    }
}