[코딩테스트] 백준 10986 자바

백준 10986

백준 10986 문제

해당 문제는 연속된 부분 구간의 합이 m으로 나누어 떨어지는 구간 합의 갯수를 출력하는 문제이다.

따라서 주어진 원본 배열의 합 배열에서 m을 나눈다. 나눈 다음에 나머지가 0이라면 처음부터 해당 값까지의 구간 합의 나머지가 0이기 때문에 정답 갯수에 추가한다.

그리고 나머지가 같은 수가 2개 이상 있을 경우,
예를 들어 1 2 1 2 1의 원본 배열 a[]가 있고, 원본 배열의 합 배열 s[]는 1 3 4 6 7이 된다.
이 중에 3으로 나누었을 때 나머지가 1인 합 배열의 원소는 1 4 7, s[0], s[2], s[4]가 된다.
여기서 큰 수 - 작은 수 → s[2] - s[0] → 4 - 1을 하면 3이 되고 나머지는 0이 된다.
결과적으로 a[1]부터 a[2]까지의 구간의 합은 3으로 나누었을 때 나머지가 0이 된다.

그리고 부분 구간의 합이 m으로 나누었을 때 0이 되는 구간 합의 갯수이기 때문에 위의 예시 같은 경우에 나머지가 1로 같은 갯수가 3개이다. 그러면 3개 중 2가지를 뽑았을 때 경우의 수를 구할 수 있다.

따라서 조합 계산식을 사용하여 3C2 = 3을 정답에 추가 해주면 된다.

package datastructure.prefixsum;

import java.util.*;

public class Boj10986 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long[] sumArr = new long[n]; // 합 배열
        long[] counts = new long[m]; // 나머지당 갯수 배열
        long answer = 0; // 정답 갯수

        sumArr[0] = sc.nextLong(); // 맨 처음 입력값 저장
        for (int i = 1; i < n; i++) {
            sumArr[i] = sumArr[i - 1] + sc.nextLong(); // 이전 값(이전까지의 합) + 현재 값으로 합 배열 초기화
        }

        for (int i = 0; i < n; i++) {
            int remainder = (int) (sumArr[i] % m); // 합 배열 값의 나머지 계산
            if (remainder == 0) { // 합 배열 값의 나머지가 0이면 처음부터 해당 값까지의 합의 나머지가 0으로 떨어지기 때문에 answer값 증가
                answer++;
            }
            counts[remainder]++; // m으로 나눈 나머지의 갯수 증가
        }

        for (int i = 0; i < m; i++) {
            if (counts[i] > 1) { // 나머지가 같은 수가 2개 이상이면
                answer = answer + (counts[i] * (counts[i] - 1) / 2); // 나머지가 같은 수의 갯수에서 2개씩을 뽑는 조합 계산하여 정답에 추가
            }
        }

        System.out.println(answer); // 정답 출력
    }
}

풀이

1. 합 배열 sumArr를 n의 크기로 선언한다.
2. 나머지당 갯수 배열 counts를 m의 크기로 선언한다.
3. 정답 answer을 0으로 초기화한다.
4. 합 배열의 0번째 값을 Scanner.nextLong()으로 넣어준다.
5. 배열의 1번째 인덱스부터 돌면서 이전까지의 구간 합 + 입력된 값으로 초기화 해준다.
6. 합 배열을 돌면서 구간 합을 m으로 나누고 나머지가 0이면 answer의 갯수를 증가시킨다.
7. 나머지가 0이 아니면 나머지에 해당하는 인덱스의 값을 증가시킨다.
8. 나머지 갯수 배열의 값이 2 이상일 때, 같은 나머지 중 큰 값을 j 작은 값을 i라고 했을 때, sumArr[j] - sumArr[i] % m은 0이 된다. 원본 배열이 a[]라고 했을 때 a[i + 1]부터 a[j]까지의 구간 합에 m으로 나눈 나머지가 0이 된다.
9. 그리고 나머지가 같은 갯수 중에서 2가지를 뽑는 경우의 수를 구해서 정답 갯수를 증가시켜준다. answer = answer + (counts[i] * (counts[i] - 1) / 2)
10. 정답을 출력한다.