BOJ_2143 : 두 배열의 합

👉 문제링크

2143번: 두 배열의 합

---

 

---

🔸 문제 분석 🔸

• 두 배열 A와 B의 부배열의 합으로 T를 만드는 경우의 수를 출력한다.

🔸 문제 풀이 🔸

• 부배열을 구하는 방법으로 누적합을 이용한다.
  • 입력 배열의 원소는 최대 1,000이므로, int형으로 2개의 배열을 선언해서 2,000 x 4Byte = 8KB가 쓰인다.
• 배열 A와 B의 누적합을 만든 뒤, 모든 부배열의 합을 구한다.
  • A의 부배열의 수는 A의 원소 수 n개 중에서 시작과 끝 인덱스 2가지를 뽑는 경우의 수이다. 이때 중복 가능하다.
    중복 조합 공식 nHr =  (n+r-1)! / r!(n-1)! 에서 r=2 이므로 다음과 같이 정리할 수 있다.
    (n+1)! / 2(n-1)!
    = n(n+1) / 2 
  • 따지고보면 1~n까지의 합을 구하는 이항계수의 공식과 같다. 2중 for문을 봤을때 더 직관적으로 알 수 있는데, 안쪽 for문의 반복 수가 n, n-1, n-2, ... , 1 순으로 줄어들기 때문이다.
  • 여기서는 n이 최대 1000이므로, 1000 * 1001 / 2 해서 최대 배열 수가 500,500 이고, A B 2개니까 1,001,000의 배열이 필요하다.
    int로 따지면 4,004,000바이트 = 4,004KB = 약 4MB 이다. 메모리 제한에 여유롭다.
• 마지막으로 A의 부배열과 B의 부배열의 합이 T가되는 경우의 수를 구한다.
  • 두 합이 T가 되도록 매칭시키는 방법으로는 투 포인터와 이진탐색 방법이 있다.
  • 투 포인터는 O(n)인데, 여기서는 중복 원소도 처리해 주어서 빠르게 탐색할 수 있다.
    • 다음과 같은 공식으로 계산한다.
      
      sum = subA[left] + subB[right]
       
    • 두 부배열합의 합이 T와 같으면, 중복 원소까지 확인해서 카운트한다.
    • T보다 크면 right - 1
    • T보다 작으면 left +1
  • 이진탐색은 평균 O(logn)이지만, 여기서는 중복 원소 때문에 4번씩 사용해야 해서 투 포인터보다 느린 결과가 나온다.
    • subA[i]를 기준값 as로 설정한다. as = subA[i]
    • subA에서 as와 일치하는 구간의 길이(일치하는 원소 수)를 구한다.
      • aTerm = upper_bound(subA, as) - lower_bound(subA, as)
      • upper_bound는 as보다 크거나 같으면서 가장 가까운 수, lower_bound는 as보다 작거나 같으면서 가장 가까운 수를 구한다.
      • 이때 as와 일치하는 원소가 여러개 이면, 그 수를 알려주게 된다.
      • 만약 as와 일치하는 원소가 없다면, 똑같이 right를 반환해 aTerm은 0이 되어 버린다.
      • bTerm는 T-as를 기준으로 구해서 aTerm과 곱하면, 경우의 수를 구할 수 있다.
    • subA의 원소를 하나씩 기준으로 넣어보며 모든 경우의 수를 누적한다.

🔸 투 포인터 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        int T = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        int[] A = new int[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            A[i] = Integer.parseInt(st.nextToken()) + A[i - 1]; // 누적합
        }

        int m = Integer.parseInt(br.readLine());
        int[] B = new int[m + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= m; i++) {
            B[i] = Integer.parseInt(st.nextToken()) + B[i - 1]; // 누적합
        }

        // 모든 부배열의 합 구하기
        int[] subA = new int[n * (n + 1) / 2]; // nC2 : 부배열 시작과 끝 인덱스 뽑기
        int[] subB = new int[m * (m + 1) / 2]; // mC2
        int idx = 0;

        for (int i = 1; i <= n; i++) { // A배열 부배열 구하기
            for (int j = i; j <= n; j++) {
                subA[idx++] = A[j] - A[i - 1]; // 부배열의 합 저장
            }
        }

        idx = 0;
        for (int i = 1; i <= m; i++) { // B배열 부배열 구하기
            for (int j = i; j <= m; j++) {
                subB[idx++] = B[j] - B[i - 1]; // 부배열의 합 저장
            }
        }

        // 투 포인터
        Arrays.sort(subA);
        Arrays.sort(subB);
        int left = 0;
        int right = subB.length - 1;
        long answer = 0;

        while (left < subA.length && right >= 0) {
            long as = subA[left];
            long bs = subB[right];
            long sum = as + bs;

            if (sum == T) {
                long ac = 0; // 같은 값 카운트
                long bc = 0;
                while (left < subA.length && as == subA[left]) {
                    left++;
                    ac++;
                }
                while (right >= 0 && bs == subB[right]) {
                    right--;
                    bc++;
                }
                answer += ac * bc;
            } else if (sum > T) {
                right--;
            } else {
                left++;
            }
        }

        // Output
        bw.write(Long.toString(answer));
        bw.flush();
    }
}

 

🔸 이분 탐색 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        int T = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        int[] A = new int[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            A[i] = Integer.parseInt(st.nextToken()) + A[i - 1]; // 누적합
        }

        int m = Integer.parseInt(br.readLine());
        int[] B = new int[m + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= m; i++) {
            B[i] = Integer.parseInt(st.nextToken()) + B[i - 1]; // 누적합
        }

        // 모든 부배열의 합 구하기
        int[] subA = new int[n * (n + 1) / 2]; // nC2 : 부배열 시작과 끝 인덱스 뽑기
        int[] subB = new int[m * (m + 1) / 2]; // mC2
        int idx = 0;

        for (int i = 1; i <= n; i++) { // A배열 부배열 구하기
            for (int j = i; j <= n; j++) {
                subA[idx++] = A[j] - A[i - 1]; // 부배열의 합 저장
            }
        }

        idx = 0;
        for (int i = 1; i <= m; i++) { // B배열 부배열 구하기
            for (int j = i; j <= m; j++) {
                subB[idx++] = B[j] - B[i - 1]; // 부배열의 합 저장
            }
        }

        // 이분 탐색
        Arrays.sort(subA);
        Arrays.sort(subB);
        long answer = 0;

        for (int i = 0; i < subA.length; i++) {
            long as = subA[i];
            long aTerm = upper_bound(subA, as) - lower_bound(subA, as);
            long bTerm = upper_bound(subB, T - as) - lower_bound(subB, T - as);
            answer += aTerm * bTerm;
            i += (int) (Math.abs(aTerm) - 1);
        }

        // Output
        bw.write(Long.toString(answer));
        bw.flush();
    }

    private static int upper_bound(int[] arr, long t) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) / 2;

            if (t >= arr[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }

    private static int lower_bound(int[] arr, long t) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) / 2;

            if (t <= arr[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
}

---

🔸 end 🔸

•  투 포인터 풀이에서, as와 bs의 곱이 int범위를 넘어서면서 68% 틀렸다.
  • n과 m이 1,000 일 때, subA와 sub의 크기가 500,500이 되고, 제곱하면 250,500,250,000가 나오기기 때문이다.
  • 백준 질문글에서 원인을 알 수 있었다.
• 알고리즘을 최대한 생각해 보았는데, 누적합까지는 생각했고 n이 1,000이니까 이분 탐색을 이용해야 하지 않을까 생각하다가 적용 법을 떠올리지 못해 풀이 포스팅을 참고했다.
  • 누적합 대신 투 포인터를 먼저 떠올렸다가 정렬이 되어있지 않아서 아니다 싶었는데, 합이 T가 되는 두 원소 찾기에서 다시 쓰일 줄 몰랐다.
  • 이분 탐색 풀이도 새롭게 알게된 부분이었는데, 범위를 이런 방식으로 구할 수 있다는게 놀라웠다.