10986. 나머지 합

📜 문제 설명

문제 설명

N개의 숫자가 주어질 때, 연속된 부분 구간 합이 M으로 나누어 떨어지는 구간의 개수

배열 [1, 2, 3, 1, 2]에서 3으로 나누어 떨어지는 구간?
👉 [1, 2], [1, 2, 3], [3], [2, 3, 1], [3, 1, 2], [1, 2] = `7개`

• N: 숫자 개수 (N ≤ 백만)
• M: 나누는 수 (M <= 1,000)
• A₁ <= 1조

숫자가 백만 개까지 주어질 수 있어서 `O(NLogN) 이하`의 시간 복잡도로 풀어야 시간 초과가 나지 않는다.

부분 구간의 개수를 구해야 하므로 계산 할 때마다 합을 구해 나가는 게 아닌, `누적합`을 이용해 풀어야 한다.

M으로 나누어 떨어지는, 즉 M으로 나눈 나머지가 0인 구간을 구하려면 `(A+B) % M == 0` 수식으로 풀면 된다.

📌 나머지 연산
(A+B)%C 는 {(A%C) + (B%C)} % C와 동일하다.
우리는 나머지 연산의 결과 값이 0인 구간을 구해야 하므로 `{(A%C) + (B%C)} % C = 0` 수식을 이용하면 된다.

---

생각 하기

[1, 2, 3, 1, 2] 배열이 주어졌을 때, 누적합을 구하면 [1, 3, 6, 7, 9]가 된다.

• 각 원소는 0부터 ~ 현재 인덱스까지의 합을 나타낸다.
• 특정 인덱스(j) ~ 현재 인덱스(i)의 부분합은 `S[i] - S[j-1]`이 된다.
  즉, S[i] - S[j]는 `j+1 ~ i` 까지의 구간 합이다.
• `S[i]%M` 값과 `S[j]%M` 값이 같은 경우, 나머지 연산에서 (S[i] - S[j])%M은 0이 된다.

우리는 누적 합을 구할 때마다 나머지 연산을 적용한 결과를 이용하면 된다.

도출해낸 규칙을 가지고 예제를 살펴보면,

• 누적합: [1, 3, 6, 7, 9]
• 나머지 저장: [1, 0, 0, 1, 0]

이때, 나머지가 0인 경우 처음부터 해당 인덱스까지의 누적합이 M으로 나누어 떨어진다는 의미이므로,
결과 값에 0의 개수를 더한다.

같은 나머지 별로 조합을 구한 후 더하면 된다.

• 나머지 1 = 2개, `₂C₂` = 1,
• 나머지 0 = 3개, `₃C₂` = 3,

따라서 구간의 개수는 3+1+3 = 7 이므로 예제의 결과값과 동일하다.

---

🍳 전체 소스 코드

import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int [] remain = new int[m];
        st = new StringTokenizer(br.readLine());
        long prev =0;
        for(int i = 0; i < n; i++) {
            int cur =Integer.parseInt(st.nextToken());
            remain[(int) ((prev + cur)%m)]++;
            prev +=cur;
        }
        long count = remain[0];
        for(int i = 0; i < m; i++) {
            count+= (long) remain[i] *(remain[i]-1) / 2;
        }
        bw.write(count+"");
        bw.flush();
        bw.close();
    }
}

---

✍ 부분 코드 설명

변수 & 배열 초기화

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int [] remain = new int[m];
        st = new StringTokenizer(br.readLine());
        long prev =0;
        for(int i = 0; i < n; i++) {
            int cur =Integer.parseInt(st.nextToken());
            remain[(int) ((prev + cur)%m)]++;
            prev +=cur;
        }
            ...

• `n`: 숫자 개수
• `m`: 나누는 수
• `remain[]`: 누적합별 m으로 나눈 나머지 저장
• `prev`: 누적합 저장

prev 변수를 `long` 타입으로 선언한 이유 ❓

주어지는 숫자의 최대 값이 1조이므로 int 타입으로 선언 시 오버플로우가 발생
int : 약 21억
long: 약 900경

반복문을 돌면서, `누적합 (prev) + 현재 값`의 나머지를 구하고, remain 배열의 해당 나머지 개수를 1 증가 한다.

---

구간 개수 구하기

public class Main{
    public static <Set> void main(String[] args) throws IOException {
             ...
        long count = remain[0];
        for(int i = 0; i < m; i++) {
            count+= (long) remain[i] *(remain[i]-1) / 2;
        }
        bw.write(count+"");
        bw.flush();
        bw.close();
    }
}

• `count`: 구간 개수 저장
  나머지가 0인 경우 그 자체로 m으로 나누어 떨어지므로 0의 개수로 count에 더한다.
• remain 배열을 순회하면서, 나머지 별 조합 개수를 구한 값을 count에 더한다.
• count 출력 후 프로그램 종료!

📌 조합 공식
₃C₂ = (3*2) / (2*1) = 3
₄C₂ = (4*3) / (2*1) = 6

count를 long으로 선언한 이유 ❓
n의 개수가 백만개이고, 나머지 값이 전부 동일한 경우, `count ≒ 5천억`이므로

---

✨ 결과

이 문제의 핵심은 나머지 연산을 활용하는 것이라고 생각한다.

처음 풀 때 나머지 연산을 변형하여 접근하는 방식을 생각하지 못 했지만,
해당 문제를 통해 구간합과 나머지 연산에 대해 정립 하고 갈 수 있었다.

문제:10986, 나머지 합