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

🧩  문제 설명

정수로 이루어진 수열이 주어졌을 때,
부분 구간의 합이 M으로 나누어떨어지는 경우의 수를 구하는 문제!

• 부분 구간은 연속된 구간이어야 함.
• 범위: 1 ≤ N ≤ 1,000,000

예시 입력:

5 3  
1 2 3 1 2

 

예시 출력:

7

---

💡 핵심 아이디어

이 문제는 완전탐색(O(N²))으로는 시간 초과가 나기 때문에
누적합(Prefix Sum) + 나머지의 개수 세기(counting)를 이용해서 O(N) 으로 해결해야 한다!

---

📌  수학 개념

sum[j] - sum[i] 가 M으로 나누어떨어진다
⟺ sum[j] % M == sum[i] % M

• 즉, 누적합의 나머지가 같은 두 시점을 고르면,
  그 사이 구간의 합은 M으로 나누어떨어짐!

---

✅  알고리즘 흐름

1. 누적합을 계산하면서 M으로 나눈 나머지를 구함
2. 나머지 값의 등장 횟수를 count 배열에 저장
3. 각 나머지 값에 대해 같은 값이 n개 등장했다면
   → nC2 = n(n-1)/2 만큼 정답 추가
4. 추가로, 누적합이 처음부터 나눠떨어지는 경우도 있으므로,
   → 나머지가 0인 경우는 바로 카운트

---

✅  예제 풀이 과정

입력: 5 3  
배열: 1 2 3 1 2

 

누적합과 나머지:

인덱스	누적합	나머지(sum % 3)
0	1	1
1	3	0
2	6	0
3	7	1
4	9	0

 

나머지 개수:

• count[0] = 3
• count[1] = 2
• count[2] = 0

정답은:

• 나머지 0인 경우 자체로 조건 만족: 3개
• count[0] → 3C2 = 3
• count[1] → 2C2 = 1
  → 총합 = 3 + 3 + 1 = 7

---

✅  자바 코드

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

public class Solution10986 {
    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());

        long[] count = new long[M]; // 나머지 개수 세기
        long sum = 0;
        long answer = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            sum += num;
            int remainder = (int)(sum % M);
            if (remainder == 0) answer++; // 바로 나눠떨어지는 경우
            count[remainder]++;
        }

        // 나머지가 같은 누적합 조합
        for (int i = 0; i < M; i++) {
            if (count[i] > 1) {
                answer += (count[i] * (count[i] - 1)) / 2;
            }
        }

        System.out.println(answer);
    }
}