[Baekjoon] 10986 - 나머지 합

📝 문제

 

 

❗ 주의

마지막 경우의 개수를 세는 변수도 long으로 선언해주어야 한다.

만약 10^6가지 수 모두 나머지가 같을때, 가능한 쌍의 개수는 (10^6) * (10^6 -1) / 2 이므로 int로 계산시 오버플로우 발생 

 

 

 

🔑 풀이 과정

이 문제는 약 2달전 코테 문제를 푼지 얼마 안됐을 때, 누적합 알고리즘을 배우면서 한 번 접했던 문제이다.

그 당시 모듈러 연산을 사용하라는 풀이를 보고도 이해가 가지 않고 해서 몇 번 시도하다가 넘어갔던 문제.

 

① 사용해야 할 알고리즘 확인

수의 개수(N)가 최대 10^6개, 주어진 시간 1초(약 10^8번 연산)이므로

이중 for문을 돌리면서 합을 구하는 것은 시간이 부족하다.

합 배열을 사용해서 누적합 알고리즘을 사용한다.

 

 

② 수의 범위를 체크

수의 개수(N)가 최대 10^6, 수의 범위가 최대 10^9 이므로

합의 최댓값은 10^15이므로 int를 넘어간다. 그러므로 합배열은 long을 사용해준다.

(앞으로는 오버플로우를 피하기 위해 되도록 int보단 long을 사용할 것)

 

 

③ 모듈러 연산의 분배법칙을 사용

(A-B) % M = ((A%M) - (B%M)) % M

우리가 찾는 것은 (Ai + ... + Aj) % M이 0이 되는 (i,j)쌍의 개수를 찾는것

이 식을 합 배열로 표현하면 (S[j] - S[i-1]) % M이 0이 되는 경우의 개수를 찾는 것

모듈러 연산의 분배법칙을 사용하여 이 식을 다시 풀면

((S[j] % M) - (S[i-1] % M)) % M 이 0이 되는 경우를 찾는 것

즉, (S[j] % M) == (S[i-1] % M) 인 경우를 찾는게 우리의 목표이다. ((S[j] % M), (S[i-1] % M)의 범위는 0이상 M미만이므로 뒤의 %M은 생략)

 

 

④ 나머지 배열을 생성

(S[i] % M) 의 값은 0이상 M미만의 값을 가진다.

나머지 배열을 생성하여 나머지가 0인경우 인덱스 0을 카운트, 1인경우 인덱스 1인 경우 카운트... 를 해준다.

예시 1로 표현하자면 다음과 같다. 

 

⑤ 가능한 쌍의 개수 계산

(1) 나머지가 0인 경우 = 입력된 수들의 1번째부터 i번째의 합이 M으로 나누어 떨어진다는 뜻

그러므로 나머지가 0인 경우의 수를 더해준다.

위 표현이 어렵다면, 이렇게 생각하기

위에서 우리가 구하는 것은
(S[j] % M) == (S[i-1] % M)
인 (i, j)쌍을 구하는 것이라 했다. (j는 i보다 크거나 같다.)

지금 이 경우는 i가 1이라서  (A1 + A2 + ... Aj)
(S[j] % M) == (S[i-1] % M)
→ (S[j] % M) == (S[0] % M)
→ (S[j] % M) == 0
인 경우인 것
===

위의 예시 1로 생각해보면
i=1, j=2
i=1, j=3
i=1, j=5
인 경우들

(2) 나머지 값이 같은 경우 중 2가지를 뽑는 경우

다만 이 경우, 뽑을 수 있는 경우가 2개 이상이어야 하므로 나머지 배열의 값이 2이상인지 체크.

순열 공식을 사용해 2가지를 뽑는 경우를 계산해서 더해준다.

nC2 = n! / (2! * (n-2)!)
→ n * (n-1) / 2

- 예시

위의 예시 1로 생각해보면


[나머지 값이 0인 경우]
3 * 2 / 2 = 3

i=3, j=3
A3 = 3 (3으로 나누어 떨어짐)
i=3, j=5
A3 + A4 + A5 = 3 + 1 + 2 = 6 (3으로 나누어 떨어짐)
i=4, j=5
A4 + A5 = 1 + 2 = 3 (3으로 나누어 떨어짐)

[나머지 값이 1인 경우]
2 * 1 / 2 = 1

i=2, j=4
A2 + A3 + A4 = 2 + 3 + 1 = 6 (3으로 나누어 떨어짐)

[나머지 값이 2인 경우]
없음

 

 

🔓 답안

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        long[] s = new long[N+1];
        long[] mod = new long[M];

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++){
            int num = Integer.parseInt(st.nextToken());
            s[i] = s[i-1] + num;
            mod[(int)(s[i]%M)]++;
        }

        long count = 0;
        count += mod[0];
        for(int i = 0; i < M; i++){
            if(mod[i] >= 2){
                count += (mod[i] * (mod[i]-1)) / 2;
            }
        }
        
        bw.write(count + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 수학

- 누적 합