BOJ 나머지 합 - 10986번 by Java

ejjem·2025년 8월 7일

목록 보기

13/20

문제 풀이 날짜: 2025-08-07

💡Github URL

https://github.com/ejjem/coding-test/tree/main/%EB%B0%B1%EC%A4%80/Gold/10986.%E2%80%85%EB%82%98%EB%A8%B8%EC%A7%80%E2%80%85%ED%95%A9

💡문제에서 구해야 할 것

문제 조건
수 N개가 주어짐.
연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수 구하기.
입력
첫째 줄에 N, M이 주어짐 (1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3)
둘째 줄에 N개의 수 A_1, A_2, ... A_N이 주어짐 (0 ≤ A_i ≤ 10^9)
출력
구간의 개수 출력

💡알고리즘 설계

구간 합 배열을 만들 듯이, 구간 합을 M으로 나눈 나머지 배열을 생성.
구간 합 배열을 만들었으므로 arr[j] - arr[i-1]과 같은 형태로 특정 구간을 찾을 건데, 이 때 나누어 떨어진다는 것은 나머지가 0이라는 것이므로 arr[j] = arr[i-1]일 때 나누어 떨어질 것.
따라서 구간 합을 M으로 나눈 나머지 배열에서 나머지가 같은 배열의 갯수를 따로 정리한 뒤, 각 나머지 별로 nC2를 진행하면 됨.
이 때, 원본 구간 합 arr[]에서 M으로 나눈 나머지가 0인 것의 갯수는 정답에 넣고 시작해야 함. 이 부분은 원본 구간 합 중에서 M으로 나누어떨어지는 구간의 갯수이기 때문.

💡코드

메모리: 120696 KB, 시간: 468 ms

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        long[] arr = new long[N];
        long[] arr2 = new long[M];
        arr[0] = Integer.parseInt(st.nextToken());
        for(int idx=1; idx<N; idx++){
            arr[idx] = arr[idx-1] + Integer.parseInt(st.nextToken());
        }
        int tmp = 0;
        long answer = 0;
        for(int idx=0; idx<N; idx++){
            tmp = (int) (arr[idx] % M );
            if(tmp == 0) answer += 1;
            arr2[tmp] ++;
        }
        
        for(int idx=0; idx<M; idx++){
            if(arr2[idx] > 1){
                answer += ( arr2[idx] * (arr2[idx] - 1) / 2 );
            }
        }
        System.out.println(answer);
    }
}

💡시간복잡도

O(N)

💡 틀린 이유 & 틀린 부분 수정

시간 초과

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N+1];
        for(int idx=0; idx<N; idx++){
            if(idx==0){
                arr[idx+1] = Integer.parseInt(st.nextToken()) % M;
            }
            else{
                arr[idx+1] = (arr[idx] + (Integer.parseInt(st.nextToken()) % M)) % M;
            }
        }
        int count = 0;
        for(int i=1; i<N+1; i++){
            for(int j=i; j<N+1; j++){
                if(arr[j] - arr[i-1] == 0){
                    count ++;
                }
            }
        }
        System.out.println(count);
    }
}

O(N^2) 라서 10^12이므로 시간 제한 1초를 넘음.

형 변환
ArrayIndexOutOfBounds, 그냥 오답 등 굉장히 많이 틀려서 뭐가 문제인지 알아내는데 오래 걸렸음.
먼저, int[] 배열을 사용해서 문제였음. 0 ≤ A_i ≤ 10^9 라서 구간합이 굉장히 커질 수 있기 때문에, 타입을 int로 사용한다면 OverFlow가 발생해 음수가 되어 버릴 수 있음. 때문에 long[] 배열로 사용해야함.
그리고, tmp = (int) (arr[idx] % M ); 이 부분을 처음에는 tmp = (int)arr[idx] % M ; 이렇게 사용했음. 생각해보니 arr[idx]가 지금 굉장히 커서 int가 아닌 long으로 사용한건데, 그걸 다시 int로 바꾸다 보니 OverFlow가 발생해 음수가 되어버리고, tmp 자체가 음수가 되어버릴 수 있는 상황이었음. 앞으로 Java에서는 수의 크기도 생각해야 할 것 같음.