[Java] 백준 10986 나머지 합

문제 

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

10986번: 나머지 합

알아야 할 개념

• 모듈러 연산 특징
• prefix sum

 

풀이

처음에 O( n logn ) 인 세그먼트 트리를 만들어서 접근하려고 했는데 역시나 O(N^2) 로 걸렸다.

이 문제의 키 포인트는 모듈러 연산의 분배법칙이다..

 

분배법칙

(a + b ) % m == a % m + b % m

풀이과정은 다음과 같다.

1. prefix sum 배열을 만든다.(누적합 배열)
2. prefix sum 배열을 탐색하면서 다음을 수행한다.
   1. 현재 i 번째 탐색일때 i-1번째까지의 mod 연산의 동치류들의 개수를 정답 변수에 더한다.( M으로 나눴을때 같은 값을 가진 것들 )
   2. 현재 M 으로 나눴을때 값을 업데이트 해준다.
3. 정답을 리턴한다.

접근 방법 tip

prefix sum 에서 구간합을 구하려면  arr[Right] - arr[Left] 으로 구한다.

문제에서 요구하는 답은 m으로 나눈 나머지가 0 인 (arr[R] - arr[L]) % m == 0 인 것들의 개수를 구해야 한다.

 

임의의 구간합 (arr[R] - arr[L] ) % m = 0 의 개수를 구해야한다.
arr[R] % m - arr[L] % m = 0 

//양변에 arr[L] % m 을 더해준다.
arr[R] % m = arr[L] % m 

즉 arr[R] % m == arr[L] % m 을 구해야한다.

이는 arr[k] % m 의 개수에서 순서 없는 조합 C 로 2개를 뽑는 경우의 수와 같다. 

 

이를 구하기 위해 for 문으로 구현한다.

for(int i = 0 ;i < N+1 ;i++){
            ans +=dp[arr[i]];//나머지가 arr[i] 인 개수들을 더한다.
            dp[arr[i]]+=1;// 나머지가 arr[i] 개수들을 +1한다.
}

코드

자바

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

public class Main {

    public static void main(String[] args) throws IOException {
        Main m = new Main();
        System.out.println(m.solution());
    }
    public long solution() throws IOException {
        FastReader fr = new FastReader();
        int N , S;
        N = fr.nextInt();
        S = fr.nextInt();
        long arr[] = new long[N+1];
        for(int i =1 ;i <= N ;i++){
            arr[i] = fr.nextInt();
        }
        //for two-pointer , convert arr elmenets
        for(int i = 1 ;i <= N ;i++)arr[i] += arr[i-1];
        //System.out.println(arr[N] + ", "+S);
        if(arr[N] < S)return 0;
        int L = 0;
        int R = 0;
        long minLen = Long.MAX_VALUE;
        while(R < arr.length && L < arr.length){
            if(arr[R]-arr[L] < S){
                R++;
            }else{
                while(L<=R && arr[R]-arr[L] >=S){
                    minLen = Math.min(minLen, R-L);
                    L++;
                }
            }
        }
        return minLen == Long.MAX_VALUE ? 0 : minLen;
    }
    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}