[백준] 11986번 - 나머지 합(Java)(△)

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

10986번: 나머지 합

 

<풀이 #1>

1. 먼저 구간 합 배열 D[N]을 구성한다.

2. 구간 합 배열을 순회하면서 M으로 나눠지는 요소를 찾아서 카운트 한다.

3. D배열 첫 인자부터 순회를 하면서 자기보다 작은 구간 합 배열을 뺐을 때 M으로 나눠지는 요소를 찾아서 카운트 한다.

  - D[i] - (D[0] ~ D[i-1])

 

<구현 #1 - 시간초과>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static int N, M;
    static int A[];
    static int D[];
    
	void Solve() {
        int count = 0;
        // 구간합 배열 요소에서 M으로 나눠떨어지는 경우의 수
        for (int i=0; i<N; i++) {
            if (D[i] % M == 0) count++;
        }
        // 구간합 배열의 부분 계산
        for (int i=1; i<N; i++) {
            for (int j=0; j<i; j++) {
                if ((D[i] - D[j])%M == 0) count++;
            }
        }
        System.out.println(count);
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = new int[N];
        D = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            if (i == 0) {
                D[i] = A[i];
            } else {
                D[i] = D[i-1]+A[i];
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }

}

시간복잡도가 O(N^2)인데 N이 1 ~ 10^6이므로 10^12가 된다. 시간제한이 1초 이므로 타임아웃이 발생한다.

 

<Hint>

 

입력값 범위가 Ai가 0 ~ 10^9 이기 때문에 구간합 배열 D[]를 int형으로 생성하면 runtime error가 발생한다.

배열 및 변수를 long으로 변경하자.

 

<구현 #2>

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

public class Main {
    static int N, M;
    static int A[];
    static long D[]; // 구간합 배열
    static long C[]; // 나머지가 같은 인덱스 개수 저장
    
	void Solve() {
        long count = 0;
        // 구간합 배열을 %M 한 나머지로 갱신
        for (int i=0; i<N; i++) {
            int remain = (int)(D[i] % M);
            // 구간합 배열 요소에서 0인 인덱스 카운트
            if (remain == 0) count++;
            //D[i] = D[i]%M;
            C[remain]++;
        }
        
        // 구간합 배열의 부분 계산
        for (int i=0; i<M; i++) {
            if (C[i] <= 1) continue; // 2개 보다 이하면 패스
            // 조합의 개수 구하는 공식 : C[i] 개수에서 2개를 고르는 모든 경우의 수
            long tmp = C[i] * (C[i]-1)/ 2;
            count += tmp;
        }
        System.out.println(count);
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = new int[N];
        D = new long[N];
        C = new long[M];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            if (i == 0) {
                D[i] = A[i];
            } else {
                D[i] = D[i-1]+A[i];
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }

}