[백준] 10986번 - 나머지 합 구하기 | Java | Python

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

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으로 나누어 떨어지는 구간의 개수를 출력한다.

 

---

제출

수학적 지식이 필요한 문제였다..
배열의 연속구간합을 sum[j] - sum[i]으로 계산하고 M으로 나누어 떨어지는 구간을 구하면, (sum[j] - sum[i])%M=0이다.
분배를 하면 sum[j]%M - sum[i]%M = 0, 고로 sum[j]%M = sum[i]%M 이다.
여기서 주의해야 할 점은 sum[i]%M = 0인 단독으로 0으로 나누어 떨어지는 경우도 미리 생각해주어야 한다는 점

 

1. Java

• 시간복잡도
  • 최악 : O(N^2) = 10^12
  • 최선 : O(N)=  10^6

import java.util.Scanner;

public class P10986 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        long[] Sum = new long[N];
        long[] Count = new long[M];
        long answer = 0;
        Sum[0] = sc.nextInt();

        for (int i=1; i<N; i++) {
            Sum[i] = Sum[i-1] + sc.nextInt();
        }

        for (int i=0; i<N; i++) {
            int remain = (int) (Sum[i] % M);
            if (remain == 0) answer++;
            Count[remain]++;
        }

        for (int i=0; i<M; i++) {
            if (Count[i] > 1) {
                answer = answer + (Count[i] * (Count[i]-1)/2);
            }
        }
        System.out.println(answer);
    }
}

 

 

 

2. Python

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = list(map(int, input().split()))
sumArr = [0] * N
sumArr[0] = arr[0]
answer = 0
for i in range(1, N):
    sumArr[i] = arr[i] + sumArr[i-1]

countArr = [0] * M
sumArr = list(map(lambda  x : x % M, sumArr))
for i in range(N):
    tmp = sumArr[i] % M
    if tmp == 0: answer += 1
    countArr[tmp] += 1

for i in range(M):
    if countArr[i] > 1:
        answer += countArr[i] * (countArr[i]-1) // 2

print(answer)