[백준][Java]나머지 합 - 10986번

쭌·2025년 10월 11일

CodingTest Java 백준

코딩테스트

목록 보기

12/16

[Gold III] 나머지 합 - 10986

문제 링크

문제 설명

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

예시

✅나의 문제 풀이

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        //N : 입력 받을 수의 갯수, M : 나눌 수
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        //합배열과 같은 나머지 인덱스 카운트 배열
        long[] S = new long[N];
        long[] C = new long[M];
        long answer = 0;

        //합배열 생성
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            //인덱스가 0이면 0-1시 예외발생하므로 if문으로 0인지 체크
            if(i==0){
                S[i] = Long.parseLong(st.nextToken());
            }else {
                S[i] = S[i - 1] + Long.parseLong(st.nextToken());
            }
        }
        //합배열의 모든값에 %M 하기
        for(int i=0; i<N; i++){
            int reminder = (int) (S[i] % M);
            //나머지가 0이면 결과값에 1씩 더하기
            if(reminder == 0) {
                answer += 1;
            }
            //나머지가 같은 인덱스의 개수 카운트하기(ex. 나머지가 1인 수가 3개면 C[1] = 3
            C[reminder]+=1;
        }

        for(int i=0; i<M; i++){
            //나머지가 같은 인덱스중 2개를 뽑는 경우의 수 이므로 인덱스의 값이 2이상인거만
            //ex. 6개면 6C2 -> 6*5 / 2 -> 15개.
            if(C[i] > 1){
                answer = answer + (C[i] *(C[i]-1)/ 2);
            }
        }
        System.out.println(answer);
    }
}

처음에 문제 이해를 못해서 많이 애먹었다...
첫번째 줄에 입력되는 첫번째 숫자N은 2번째 줄의 숫자의 갯수고, 그 다음 입력되는 M은 나누어 떨어지는 수(나눌 수)를 의미한다.
그리고 합이 M으로 나누어 떨어지는 (i,j)쌍의 개수를 구하라고 하는데, 예시의 1 2 3 1 2를 예로 들어보자면

인덱스1 부터
- A[1] = 1 → 나머지3
- A[1]+A[2] = 1+2 = 3 → 나머지0
- A[1]+A[2]+A[3] = 1+2+3 = 6 → 나머지0
- A[1]+A[2]+A[3]+A[4] = 1+2+3+1 = 7 → 나머지1
- A[1]+A[2]+A[3]+A[4]+A[5] = 1+2+3+1+2 = 9 → 나머지0
인덱스2 부터
- A[2] = 2 → 나머지1
- A[2]+A[3] = 2+3 = 5 → 나머지1
- A[2]+A[3]+A[4] = 2+3+1 = 6 → 나머지0
- A[2]+A[3]+A[4]+A[5] = 2+3+1+2 = 8 → 나머지2

...

이런식으로 누적합을 더해서 그 누적합에서 m으로 나눴을 때 나누어떨어지는 쌍의 개수를 구하는 것이다.

문제 풀이 순서

1. 원본 배열인 A배열의 합배열 S를 생성한다.

S[i] = S[i-1] + A[i]

2. 합 배열 S의 모든 값에 대해 M으로 나머지 연산을 수행하여 합배열을 업데이트 한다

여기서 이해가 안될 수도 있는데, 1에서 구한 합배열을 M(예시에선 3)으로 나머지 연산을 수행하고, 해당 값의 나머지를 배열의 값으로 업데이트 하는것이다.
그리고 배열의 원소값이 0인 개수를 정답에 더한다.
예시에서는 나머지가 0인 인덱스가 3개이므로 3을 더한다.
이렇게 하는 이유는 원소의 값이 0이라는 뜻은 원본 배열의 0부터 i까지의 구간 합이 이미 M으로 나누어 떨어진다는 뜻이기 때문!