[10986] 나머지 합

✔ 나머지 합

[백준 10986]

문제 분석하기

구간 합 배열을 이용해 계산하며

특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값을 동일하다는 것을 이용함

또한 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[j]와 S[i]가 같은 (i, j) 쌍을 찾으면
원본 배열에서 i + 1부터 j까지의 구간 합이 M으로 나누어 떨어짐을 이용함

예) S[0] = S[3] = 1 이므로 A[1]부터 A[3]까지의 구간 합이 M으로 나누어 떨어짐 (1 + 2 + 3 + 1 - 1 = 6 % 3 = 0)

손으로 풀어보기

1. A 배열의 합 배열 S를 생성
2. 합 배열의 S의 모든 값을 M으로 나누어줌
3. 원소 값이 0인 경우, 원본 배열의 0부터 i까지의 구간 합이 이미 M으로 나누어 떨어지므로 이 개수만 세어 정답에 더함
   • 경우의 수 = +3
     • A[0] ~ A[1] = (1 + 2) % 3 = 0
     • A[0] ~ A[2] = (1 + 2 + 3) % 3 = 0
     • A[0] ~ A[4] = (1 + 2 + 3 + 1 + 2) % 3 = 0
4. 원소 값이 같은 합 배열의 경우에 대해 모든 경우의 수를 구하여 정답에 더함
   • 3C2, 경우의 수 = +3
     • A[2] ~ A[2] = 3 % 3 = 0
     • A[2] ~ A[4] = (3 + 1 + 2) % 3 = 0
     • A[3] ~ A[4] = (1 + 2) % 3 = 0
   • 2C2, 경우의 수 = +1
     • A[1] ~ A[3] = (2 + 3 + 1) % 3 = 0

배열 A

1

2

3

1

2

합 배열 S

1

3

6

7

9

변경된 합 배열 S

1

0

0

1

0

슈도코드 작성하기

N 입력받기(수열의 개수)
M 입력받기 (나누어떨어져야 하는 수)
S 선언하기 (합 배열)
C 선언하기 (같은 나머지의 인덱스를 카운트하는 배열)
for(i -> 1 ~ N) {
    S[i]= S[i - 1] + A[i]
}
for(i -> 0 ~ N) {
    remainder = S[i] % M
    if(remainder == 0) 정답을 1 증가시키기
    C[remainder]의 값을 1 증가시키기
}
for(i -> 0 ~ M) {
    C[i](i가 나머지인 인덱스의 개수)에서 2가지를 뽑는 경우의 수를 정답에 더하기
}
결괏값(answer) 출력

코드 구현하기

/**
 * 10986) 나머지_합
 */
public class D005_10986 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N 입력받기(수열의 개수)
        int N = sc.nextInt();
        // M 입력받기 (나누어떨어져야 하는 수)
        int M = sc.nextInt();
        // S 선언하기 (합 배열)
        long[] S = new long[N];
        // C 선언하기 (같은 나머지의 인덱스를 카운트하는 배열)
        long[] C = new long[M];
        long answer = 0;
        // 수열 합 배열 만들기
        S[0] = sc.nextInt();
        for (int i = 1; i < N; i++) {
            S[i] = S[i - 1] + sc.nextInt();
        }
        // 합 배열의 모든 값에 % 연산 수행하기
        for (int i = 0; i < N; i++) {
            int remainder = (int) (S[i] % M);
            // 구간 합 자체가 0일 때 정답에 더하기
            if (remainder == 0)
                answer++;
            // 나머지가 같은 인덱스의 개수 카운팅하기
            C[remainder]++;
        }
        for (int i = 0; i < M; i++) {
            // 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 더하기
            if (C[i] > 1)
                answer = answer + (C[i] * (C[i] - 1) / 2);
        }
        System.out.println(answer);
    }
}