[백준] 10986 나머지 합

 

 

 

문제 출저

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

10986번: 나머지 합

 

 

 

문제 풀이

수 N개가 주어집니다. 이 떄 연속된 부분 구간 합이 M으로 나누어 떨어지는 구간의 개수를 구해야 합니다.

 

 

누적합으로 풀었습니다. 

int[] prefix 라는 1차원 정수 배열로 누적합을 만들었습니다. 

int[] remainder 라는 1차원 정수 배열로 누적합을 m으로 나눈 나머지의 갯수를 저장했습니다.

그 누적합의 갯수를 이용해 2개를 선택하는 경우의 수를 계산해 정답을 구했습니다.

 

 

 

소스 코드

package baekjoon.backjoon10.day2131.day26;

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

/*
나머지 합
https://www.acmicpc.net/problem/10986


 */
public class B10986 {

    static int n,m;
    static int[] board;
    static long[] prefix;
    static int[] remainder;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(st.nextToken());
        }

        prefix = new long[n];
        long before = 0;
        for(int i = 0; i < n; i++) {
            prefix[i] = before + board[i];
            before = prefix[i];
        }

        long answer = 0;
        remainder = new int[m];
        /*
        런타임 에러 (ArrayIndexOutOfBounds) -> 에러 터진 지점
        연산을 한 다음에 형변환을 하자
           for(int i = 0; i < n; i++) {
            int number = (int) prefix[i] % m;
            if(number == 0) {
                answer += 1;
            }
            remainder[number] += 1;
        }
         */
        for(int i = 0; i < n; i++) {
            long number = prefix[i] % m;
            if(number == 0) {
                answer += 1;
            }
            remainder[(int) number] += 1;
        }

        for(int i = 0; i < m; i++) {
            if(remainder[i] >= 2) {
                answer += (((long) remainder[i] * (remainder[i]-1)) / 2);
            }
        }

        System.out.println(answer);



    }


}