📢 이번 문제는 합배열과 누적합에 대한 사전지식이 필요합니다! 합배열과 누적합에 대한 설명이 필요하다면 아래의 글을 참고해주세요 😉
[Java/백준 11659] 구간 합 구하기4

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.
백준 10986 상세보기
❗ 시간 제한이 1초임을 고려해야 한다.

분석

구간 합(S[j]-S[i-1])을 M으로 나눈 나머지가 0인 (i, j)의 값을 구해야한다.
수학적으로 정리해보면 다음과 같다.

1. $(S[j]$ $-$ $S[i-1])$ % $M$ $= 0$
2. $(S[j]$ % $M)$ $-$ $(S[i-1]$ % $M)$ $= 0$
3. $S[j]$ % $M=$ $S[i-1]$ % $M$

위의 식을 토대로 구현해야할 코드를 단계적으로 생각해보자.

1. 합배열 s를 생성할 때, %M 처리한 결과를 저장한다.
   
2. S[i] % M == 0 인 수를 세어 결과 값에 더한다.
   S[i] % M 값이 0이라는 뜻은 원본 배열 A의 (1~i)의 구간 합이 이미 M으로 나누어 떨어진다는 뜻이기 때문이다.
   
3. S[j] % M == S[i-1] % M 을 만족하는 (i,j)의 수를 구한다. 즉, 나머지 값이 같은 인덱스 중 2개를 뽑는 모든 경우의 수를 구하면 된다.
   • 나머지 값이 같은 인덱스의 수를 저장하기 위한 배열 cnt를 생성한다.
     이때, M으로 나눈 나머지가 될 수 있는 수는 0부터 M-1까지 가능하다. 따라서 크기가 M인 배열을 생성한다.
     
   • cnt 배열을 통해 나머지 값이 같은 인덱스 중 2개를 뽑는 모든 경우의 수를 구한다. 위의 예에서는 0이 3개, 1이 2개이므로 $_3C_2$와 $_2C_2$의 합을 구하고 결과 값에 더한다.
     $_nC_r$ : n개 중에서 r개를 뽑는 모든 경우의 수
     

소스 코드

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

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 1. N(수의 개수), M(나누기 할 수) 입력받기
        int N = Integer.parseInt(st.nextToken());   // 수의 개수
        int M = Integer.parseInt(st.nextToken());   // 나누기 할 수
        long result = 0;                            // M으로 나누어떨어지는 (i,j) 쌍의 개수
        long[] S = new long[N + 1];                 // 합배열
        long[] cnt = new long[M];                   // 같은 나머지의 인덱스를 카운트하는 배열

        // 2. N개의 수 입력받으면서 누적합을 M으로 나눈 나머지를 배열 S에 저장한다.
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            S[i] = (S[i - 1] + Integer.parseInt(st.nextToken())) % M;
            // 0~i까지의 합을 M으로 나눈 나머지가 0인 경우의 수 카운팅
            if(S[i] == 0) {
                result++;
            }
            // 나머지가 같은 인덱스의 수 카운팅
            cnt[(int) S[i]]++;
        }

        // 3. S[j] % M == S[i-1] % M 을 만족하는 (i,j)의 수를 결과값에 더한다.
        // 즉, cnt[i](i가 나머지인 인덱스의 수)에서 2가지를 뽑는 경우의 수 카운팅한다.
        for(int i=0; i<M; i++) {
            if(cnt[i] > 1) {
                result += (cnt[i]* (cnt[i]-1) / 2);
            }
        }
        System.out.println(result);
    }
}

풀이 정리

Tip 1. 시간 제한을 고려하자 !

사실 이번 문제는 시간 제한이 없었더라면 간단하게 풀 수 있었을지도 모른다. 첫번째 시도에는 중첩 반복문을 통해 모든 구간 합 중에서 S[j] - S[i-1]) % M == 0 조건을 만족하는 수를 구하는 코드를 작성했지만 시간 초과로 실패했다😂 아무래도 모든 구간 합을 검사하는 부분에서 시간이 오래 걸린것 같다.
아래의 코드는 첫번째로 작성했던 코드이다.

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String args[]) throws IOException {
        // 1. N(수의 개수), M(나누기 할 수) 입력받기
        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());

        // 2. N개의 수 입력받으면서 누적합 배열 S 생성하기
        st = new StringTokenizer(br.readLine());
        int[] S = new int[N+1];
        for(int i=1; i<N+1; i++) {
            S[i] = S[i-1] + Integer.parseInt(st.nextToken());
        }

        // 3. 구간 합(S[j]-S[i-1])를 M으로 나누었을 때 나머지가 0이 되는 (i,j) 쌍의 개수 계산
        int cnt = 0;
        for(int i=1; i<N+1; i++) {
            for(int j=i; j<N+1; j++) {
                if((S[j] - S[i-1]) % M == 0) {
                    cnt++;
                }
            }
        }

        System.out.println(cnt);
    }
}

Tip 2. 수학 계산을 활용하자 !

1초의 시간 제한을 맞추기 위해서는 연산을 줄일 수 있는 방법이 필요하다.
이번 문제에서는 $S[j]$ % $M=$ $S[i-1]$ % $M$ 를 도출하는 것과 조합( $_nC_r$ )을 사용하는 방법이 있었다. 물론 단번에 생각해내기는 어렵겠지만..😅 이번 기회를 통해 이런 방법도 있다는 것을 기억해두면 좋을 것 같다!

Tip 3. 오버플로우가 발생하지는 않는지 확인하자 !

연산 과정을 줄인 코드로 다시 시도했지만 또 다시 틀렸다는 결과가 나왔다. 다른 코드들과 비교해보니 데이터 타입이 int가 아닌 long타입으로 선언되어 있는 것을 발견했다.
문제의 입력 조건을 고려하면 int 타입이 모든 테스트 데이터를 수용하지 못한 것이 원인이 된 것 같다.👀

• $1 ≤ N ≤ 10^6$
• $2 ≤ M ≤ 10^3$
• $0 ≤ Ai ≤ 10^9$

정수형 데이터의 타입을 결정할 때는 반드시 사용하고자 하는 데이터의 최대 크기를 고려해야 한다. 해당 타입이 표현할 수 있는 범위를 벗어난 데이터를 저장하면, 오버플로우가 발생해 전혀 다른 값이 저장될 수 있다.

• 오버플로우(overflow)
  : 해당 타입이 표현할 수 있는 최대 범위보다 큰 수를 저장할 때 발생하는 현상
• 언더플로우(underflow)
  : 해당 타입이 표현할 수 있는 최소 범위보다 작은 수를 저장할 때 발생하는 현상

💡 Java의 정수형 데이터 타입 중에서 long 타입이 데이터의 표현 범위가 가장 넓다! 따라서 코딩 테스트에서는 처음부터 long형으로 선언하는 것이 좋을 것 같다!

---

Reference

[book] Do it! 알고리즘 코딩 테스트 - 자바 편
기본 타입(primitive type) - 코딩의 시작, TCP School