녕의 학습 기록

백준_10986 나머지 합 (구간합배열) 본문

Algorithm/Algorithm 문제

백준_10986 나머지 합 (구간합배열)

kjyyjk 2023. 11. 21. 22:58

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_10986 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int i, temp;
        long result = 0;

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        long[] arrSum = new long[n+1];
        long[] remainderArr = new long[m];

        st = new StringTokenizer(br.readLine(), " ");

        // 구간합배열 계산
        for(i=1; i<n+1; i++) {
            arrSum[i] = arrSum[i-1] + Long.parseLong(st.nextToken());
        }

        // 구간합배열에 %m연산
        // 이때 값이 0이면 (1,i)구간이 정답케이스라는 것이므로 result 1 증가
        // %m연산한 후 같은 값을 가지는 구간도 역시 정답케이스. 경우의수 계산을 위해 각 값을 인덱스로 가지는 나머지배열 이용
        for(i=1; i<n+1; i++) {
            temp = (int) (arrSum[i]%m);
            if(temp==0) {
                result++;
            }
            remainderArr[temp]++;
        }

        //나머지 배열에서 경우의 수 계산. ex) 1번 인덱스의 값이 4면 4C2 계산 시 구간의 수 나옴
        //주의할건 0도 포함해야함. 위에서 정답케이스로 매긴 0은 (1번~해당인덱스까지합)이고
        //여기서 0은 (0값 가지는 인덱스 ~ 0값 가지는 인덱스) 구간. 다르다.
        for(i=0; i<m; i++) {
                result += (remainderArr[i] * (remainderArr[i]-1) / 2);
        }

        StringBuilder sb = new StringBuilder();
        sb.append(result).append('\n');

        System.out.println(sb);

    }

}

 

 

 

10986번: 나머지 합

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

www.acmicpc.net