백준 10986 Java 풀이: 누적합 나머지로 구간 합 개수 세기

백준 10986번 ‘나머지 합’은 합이 M으로 나누어떨어지는 연속 부분 구간의 개수를 구한다. 모든 구간을 이중 반복문으로 확인하면 입력 크기를 감당할 수 없다. 핵심은 나머지가 같은 두 누적합의 차는 M의 배수라는 성질이다.

• 백준 10986번 문제

같은 나머지를 묶는 이유

prefix[i]를 1번부터 i번까지의 합이라고 하자. 구간 i+1..j의 합은 다음과 같다.

prefix[j] - prefix[i]

두 누적합을 M으로 나눈 나머지가 같으면 차의 나머지는 0이다.

prefix[j] % M == prefix[i] % M
→ (prefix[j] - prefix[i]) % M == 0

따라서 각 나머지가 몇 번 나타났는지만 세면 된다. 나머지 r이 c번 나타났다면 그중 두 위치를 고르는 경우의 수는 c × (c - 1) / 2다.

빈 누적합을 먼저 넣기

배열을 읽기 전 누적합 0도 하나의 위치로 포함한다.

remainderCount[0] = 1;

그러면 처음부터 현재 위치까지의 합이 M의 배수인 경우도 별도 예외 처리 없이 같은 조합식에 들어간다.

예제 M = 3, 수열 [1, 2, 3, 1, 2]의 누적합 나머지는 빈 누적합을 포함해 다음과 같다.

0, 1, 0, 0, 1, 0

• 나머지 0: 4개 → 4C2 = 6
• 나머지 1: 2개 → 2C2 = 1

답은 7이다.

Java 코드

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

public class Main {
    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[] remainderCount = new long[m];
        remainderCount[0] = 1;

        int prefixRemainder = 0;
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            int value = Integer.parseInt(st.nextToken());
            prefixRemainder = (prefixRemainder + value) % m;
            remainderCount[prefixRemainder]++;
        }

        long answer = 0;
        for (long count : remainderCount) {
            answer += count * (count - 1) / 2;
        }

        System.out.println(answer);
    }
}

왜 long이 필요한가

같은 나머지를 가진 누적합이 많으면 조합 수가 매우 커진다. 최대 약 N × (N + 1) / 2개의 구간이 답이 될 수 있으므로 int 범위를 넘는다. remainderCount와 answer를 long으로 두면 곱셈도 처음부터 long으로 계산된다.

누적합 전체를 저장할 필요는 없다. 직전 나머지에 현재 값을 더하고 다시 M으로 나눈 값만 유지하면 된다.

당시 풀이에서 남은 것

이 문제는 거의 하루 반나절을 고민한 뒤 질문 게시판의 힌트와 다른 분들의 도움을 받아 풀었다. 처음에는 누적합을 만들고 모든 구간을 비교하는 데서 막혔고, 같은 나머지끼리 묶는다는 전환이 쉽게 떠오르지 않았다.

이 풀이를 마친 무렵 알고리즘 등급 Gold I도 달성했다. 당시 글에는 스스로 ‘물골드’라고 낮춰 적었지만, 오래 고민하고 도움을 받아 원리를 이해한 과정도 함께 남길 만하다.

복잡도

• 시간 복잡도: O(N + M)
• 공간 복잡도: O(M)

누적합 문제를 볼 때 배열 전체를 만드는 것보다, 구간 조건을 만족시키는 두 누적 상태의 관계를 먼저 찾는 습관을 남긴 문제다.