백준 10986 : 나머지 합

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

10986번: 나머지 합

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

 

문제 분석하기

(A + B) % C 는 ((A % C) + (B % C)) % C와 같다

따라서, S[j] % M의 값과 S[i] % M의 값이 같으면 (S[j] - S[i) % M은 0이고

여기서 S[j] - S[i]는 원본 배열의 i+1부터 j까지의 구간 합이다

 

결론: 구간합 배열의 원소를 M으로 나눈 나머지로 업데이트 하고 S[j]와 S[i]가 같은 (i,j)쌍을 찾으면 답을 도출할 수 있다

 

문제 풀기

1. 일반 배열 A를 통해 구간 합 배열 S를 생성한다
2. S의 모든 값을 M으로 나누어 나머지 연산을 수행하여 S 원소 값을 업데이트 한다
3. 나머지의 숫자가 같은 경우를 일일이 계산해주는 배열 C를 생성한다.
4. 숫자가 같은 원소를 2개씩 고르는 조합계산을 수행해주어 답을 도출한다

코드

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

public class n11986 {
    public static void main(String[] args) throws IOException{
        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()); 

        long[] C = new long[M];

        long sum = 0;
        int remainder = 0;
        long answer = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            sum = sum + Integer.parseInt(st.nextToken()); 
            remainder = (int) (sum % M);
            C[remainder]++;
        }
        
        
        answer = C[0];
        for (int i=0;i<M;i++){
            if (C[i]>1){
                answer += C[i] * (C[i]-1)/2;
            }
        }
        System.out.println(answer);

    }
}

 

배운 점

1. int? long?

i*(i-1)이 계산되는 과정에서 오버플로우가 일어날 수 있습니다.

 

2. 배열의 크기

문제의 N의 값은 1보다 크거나 같은데 N이 1이 들어온다면 
sum[i] = sum[i-1] + Long.parseLong(st.nextToken()); 이 부분에서 오류날 거 같아요 !

 

2. 배열의 사용

구간 합 배열을 사용하다 보니
런타임 에러 (ArrayIndexOutOfBounds) 
라는 에러가 계속 발생하였다
그래서 구간 합 배열을 사용하지 않고 풀어 보니 통과할 수 있었다
-> 결론 : 변수의 범위가 너무 크면 배열 지양? (이건 근데 내가 아직 문제를 몇개 못풀어서 뇌피셜...인듯)

 

참고 도서 : Do it! 알고리즘 코딩 테스트 - 자바 편