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

🚀 문제 핵심

N개의 수에서 연속된 부분 구간의 합이 M으로 나누어떨어지는 구간의 개수를 구하는 문제입니다. 1차원 구간 합의 심화 버전으로, 단순 누적 합을 넘어 나머지 연산의 성질을 이용해야 합니다.

---

💡 핵심 원리: 나머지 구간 합 (Modulo Prefix Sum)

구간 $(i, j)$의 합이 $M$으로 나누어떨어진다는 것은 다음과 같은 수식으로 표현됩니다.

• $(S[j] - S[i-1]) \pmod M = 0$
  $\Rightarrow S[j] \pmod M = S[i-1] \pmod M$

즉, "누적 합을 M으로 나눈 나머지가 같은 두 지점을 선택"하면 그 사이의 구간 합은 무조건 M으로 나누어떨어집니다.

1. 수학적 설계: 조합(Combination)
   나머지가 같은 지점이 $k$개 있다면, 그중 2개를 선택하는 경우의 수인 $_kC_2$가 곧 조건을 만족하는 구간의 개수가 됩니다.

• 공식: $\frac{k(k-1)}{2}$

2. 최적화: 공간 복잡도 줄이기
   보통은 prefixSum[] 배열을 만들어 나머지를 저장한 뒤 다시 카운팅하지만, 이번 풀이에서는 배열 없이 실시간으로 나머지만 계산하여 카운팅을 진행했습니다.

• 기존: $O(N)$ 공간 사용 (누적 합 배열)
• 최적화: $O(M)$ 공간 사용 (나머지 카운팅 배열만 유지)

---

🧐 설계 포인트: count[0] = 1의 의미

코드에서 가장 중요한 디테일입니다.

• 나머지가 0인 지점이 $k$개일 때, $_kC_2$는 "나머지가 0인 지점 두 개를 골라 그 사이 구간을 만드는 경우"입니다.
• 하지만 나머지가 0인 지점 그 자체(1번부터 해당 지점까지)도 정답에 포함되어야 합니다.
• 이를 위해 count[0]을 1로 미리 설정해두면, 별도의 조건문 없이 $_kC_2$ 공식 하나로 모든 케이스를 완벽하게 처리할 수 있습니다.

---

💻 구현 코드 (Java)

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

public class Main {
    public static void main(String[] args) throws Exception {
        try (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());

            st = new StringTokenizer(br.readLine());
            
            // 나머지의 개수를 저장할 배열 (공간 최적화: O(M))
            int[] count = new int[m];
            int prev = 0;
            
            // 나머지가 0인 지점 자체를 처리하기 위한 초기화
            count[0] = 1;

            for (int i = 0; i < n; i++) {
                // 실시간으로 누적 합의 나머지를 계산
                int cur = (prev + Integer.parseInt(st.nextToken())) % m;
                // 음수 나머지가 나올 수 있는 경우 (cur + m) % m 처리가 필요하지만, 
                // 이 문제는 양수 조건이므로 생략 가능
                count[cur]++;
                prev = cur;
            }

            long answer = 0;
            for (int c : count) {
                // 나머지가 같은 지점 k개 중 2개를 고르는 조합 (kC2)
                // 결과값이 int 범위를 넘을 수 있으므로 long 형변환 필수
                answer += (long) c * (c - 1) / 2;
            }
            System.out.println(answer);
        }
    }
}

---

✅ Tip: 왜 long인가?

결과값 answer를 계산할 때 반드시 long을 사용해야 합니다.

• $N$이 100만일 때, 모든 누적 합의 나머지가 같다면 $_kC_2$는 약 $5,000$억에 육박합니다. 이는 int 범위를 훌쩍 뛰어넘으므로 주의가 필요합니다.

---

🎯 마치며

누적 합 배열을 직접 만들지 않고도 문제를 해결하는 최적화 과정을 통해 알고리즘의 효율성을 한 단계 더 높였습니다. 나머지의 성질과 조합론을 결합한 이 방식은 코딩 테스트에서 매우 자주 출제되는 패턴이니 꼭 숙지해두면 좋습니다.