[Java] 백준 10986번 문제(나머지 합)

원본 출처 : https://www.acmicpc.net/problem/10986

 

문제설명

 

 

소스코드

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

public class Boj_10986
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // n과 m을 받아옴
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 합과 나머지의 수를 저장하는 배열 생성
        long[] sumArr = new long[N + 1]; // 합 배열
        long[] remainArr = new long[M]; // 합 배열을 M으로 나눴을 때 나머지의 수를 저장하는 배열 -> 나머지 배열과 다름
        long count = 0;

        // 합 배열 및 나머지의 수를 저장하는 배열을 구함
        // 1차적으로 값을 구함
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < sumArr.length; ++i)
        {
            sumArr[i] = Integer.parseInt(st.nextToken()) + sumArr[i - 1];
            int remainder = (int) (sumArr[i] % M); // 합 배열을 M으로 나눈 값
            if(remainder == 0) ++count; // 나머지가 0인 개수를 카운트
            ++remainArr[remainder]; // 나머지의 수를 저장하는 배열의 '합 배열을 M으로 나눈 값'을 인덱스로 가지는 값을 증가시킴
        }

        // 나머지 배열에서 원소 값이 같은 개수를 더함(조합)
        // 원소 값이 같은 2개의 원소를 뽑는 모든 경우의 수
        for(int i = 0; i < M; ++i)
        {
            if(remainArr[i] > 1) count += (remainArr[i] * (remainArr[i] - 1) / 2);
        }

        System.out.println(count);
    }
}

 

설명

핵심 아이디어

• (A + B) % C는 ((A % C) + (B % C)) % C와 같다.
  = 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.
• 구간 합 배열을 이용한 식 합배열[j] - 합배열[i]는 원본 배열의 i + 1 부터 j까지의 구간 합이다.
• 합배열[j] % M의 값과 합배열[i]의 값이 같다면 (합배열[j] - 합배열[i]) % M은 0이다.
  = 구간 합배열의 원소를 M으로 나눈 나머지 배열에서 나머지 배열[j] = 나머지 배열[j]가 같은 (i, j) 쌍을 찾으면 원본 배열에서 i + 1부터 j까지의 구간 합이 M으로 나누어 떨어진다.

합배열[j] % M의 값과 합배열[i] % M의 값이 같다면 (합배열[j] - 합배열[i]) % M은 0이다.
= 구간 합배열의 원소를 M으로 나눈 나머지 배열에서 나머지 배열[j] = 나머지 배열[j]가 같은 (i, j) 쌍을 찾으면 원본 배열에서 i + 1부터 j까지의 구간 합이 M으로 나누어 떨어진다.

나머지 배열에서 원소 값이 0인 개수만 세어서 정답에 더한다

나머지 배열의 원소 값이 0이라는 뜻은 원본 배열의 0부터 i까지의 구간 합이 이미 M으로 나누어 떨어진다는 뜻이기 때문

위 예에서는 나머지 배열의 값이 0인 경우가 3개이므로

 

나머지 배열에서 원소 값이 같은 배열의 개수를 센다.

나머지 배열에서 원소 값이 같은 2개의 원소를 뽑는 모든 경우의 수를 구해서 정답에 더하면 된다.

->그렇기 때문에 합 배열을 M으로 나눴을 때 나머지의 수를 저장하는 배열을 코드에서 선언해줘야 한다.

 

위 예에서는 0이 3개, 1이 2개 이므로

 

마지막으로 합 배열은 누적합을 저장하므로 int가 아닌 long으로 선언 해주어야 하고,

값을 출력하는 변수도 구간의 개수를 누적하는 역할을 하기 때문에, 최대 10⁶개의 원소에서 O(N) 연산을 수행하면, 결과적으로 count 값이

10^12정도 될 가능성이 있다. 그렇기 때문에 이 또한 long으로 선언해주어야 한다.

 

글과 그림으로 이해가 안된다면, 아래의 영상을 보고 이해하는 것이 좋다.

https://www.youtube.com/watch?v=Ud-qe0t5KA8&ab_channel=%ED%95%98%EB%A3%A8%EC%BD%94%EB%94%A9