[BOJ 10986] 나머지 합 (Java)

BOJ 10986 나머지 합

난이도 : 골드 3

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

전략

수열의 길이 N은 최대 10^6이므로 모든 부분 구간을 탐색하는 O(N^2)으로는 풀 수 없다.

누적 합을 이용하면 두 지점 사이의 부분 배열의 합을 구할 수 있다.

나는 누적합 % M이 반복되었을 때 해당 구간의 합 % M은 0이 되는 것을 주목했다.

문제의 예제를 예로 들어보자.

N = 5, M = 3

수열 :             1 2 3 1 2

누적합 % M : 1 0 0 1 0

값이 0이 되는 지점은 당연히 포함해야되며

0이 아닌 지점은 반복되는 곳을 잘 봐야한다.

1이 처음 등장할 때는 당연히 % M이 0이 될 수 없지만,

두번째 등장할 때는 두 지점 사이의 부분합의 % M은 0이 된다.

 

만약 여러번 등장한다면 어떻게 될까?

index 0, 3, 5에서 % M이 1이 되었다면

0 ~ 3 구간, 0 ~ 5구간, 3 ~ 5구간이 포함되어야 한다.

T번째로 % M이 1이 된다면 + (T - 1)만큼 해줘야 된다.

 

따라서 M 크기의 배열을 이용해 % M이 각 몇번 등장하는지 기록해놓으면서 진행하면 O(N)에 계산이 가능하다.

M은 최대 10^3이므로 공간도 충분하다.

 

주의할 점은 0은 한번만 나와도 개수를 세어야 하고, 나머지는 두번째부터 개수를 세어야한다.

따라서 나는 두 경우를 분리해서 전위/후위 연산으로 구현했다.

 

시행착오

결과를 int로 저장했었는데, N^2만큼 커질 수 있으므로 long으로 변경했다.

 

코드

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));
        int N, M;
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] cnt = new int[M];

        long sum = 0;
        long ans = 0;

        for (int i=0; i<N; i++) {
            sum += Integer.parseInt(st.nextToken());
            int idx = (int) (sum % M);
            if (idx == 0)
                ans += ++cnt[idx];
            else
                ans += cnt[idx]++;
        }
        System.out.println(ans);
    }
}

누적 합 외에는 다른 정보가 필요 없어서 수열은 따로 저장하지 않고 입력 받으면서 진행했다.

 

사실 모듈러의 성질 때문에 sum을 int로 잡고 계속 mod 연산을 해줘도 상관은 없다.

하지만 최대 10^9인 수를 10^3 번 더해도 long으로 표현가능하므로 그냥 간단하게 표현했다.