[백준] 2143번 두 배열의 합

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   한 배열 A[1], A[2], ..., A[n]에 대해서, 부 배열은 A[i], A[i+1], ...,A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i] + ... + A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 문제이다.

   예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

 

T(=5) = A[1] + B[1] + B[2]
      = A[1] + A[2] + B[1]
      = A[2] + B[3]
      = A[2] + A[3] + B[1]
      = A[3] + B[1] + B[2]
      = A[3] + A[4] + B[3]
      = A[4] + B[2] 

 

   첫째 줄에 합 T가 주어지며, 다음 줄에는 n이 주어지고, 그 다음 줄에 n개의 정수로 A[1], ..., A[n]이 주어진다. 다음 줄에는 m이 주어지고, 그다음 줄에 m개의 정수 B[1], ..., B[m]이 주어진다.

   제한 사항은 다음과 같다.

 

• -1,000,000,000 ≤ T ≤ 1,000,000,000
• 1 ≤ n ≤ 1,000
• 1 ≤ m ≤ 1,000
• -1,000,000 ≤ 각 배열의 원소 ≤ 1,000,000
• 가능한 경우가 없는 경우 0을 출력

---

접근 방식

   누적합의 개념을 이용해 문제를 해결하였다. T가 되는 부 배열 쌍의 개수를 구하기 위해 각 배열을 이용해 만들 수 있는 부 배열의 값과 그 값이 만들어지는 경우의 수를 알아야 한다. 한 단계씩 차근차근 알아가 보자.

   우선 누적합 구간의 합을 빠르게 구하기 위해서 이용된다. 배열에서 특정 범위의 합을 구하고 싶을 때 인덱스를 탐색하며 값을 하나씩 더하는 방법도 있지만 이런 방법은 배열의 크기가 커질수록 비효율적이다. 따라서 현재 인덱스의 값이 이전 인덱스의 값을 포함하는 형태로 배열의 값을 초기화 함으로써 특정 범위의 합을 다음과 같이 구할 수 있다.

 

 

   즉, i ~ j까지 구간의 합을 구하고 싶다면 j번째 인덱스의 값에서 i-1번째 인덱스의 값을 빼주면 된다. 이로써 구간의 합을 빠르게 구할 수 있게 되었다. 이 방법을 이용해 배열의 부 배열을 구해보자.

   위의 예제에서 소개한 배열을 이용해 하나씩 경우의 수를 구해보면 다음과 같다.

 

• 1개 : 1, 2, 3, 4, 5, 6
• 2개 : 3, 5, 7, 9, 11
• 3개 : 6, 9, 12, 15
• 4개 : 10, 14, 18
• 5개 : 15, 21
• 6개 : 21
• 만들 수 있는 값 15개 : 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 14, 15, 18, 21

   모든 부 배열을 확인하는 방식은 범위의 크기를 늘려가며 진행하였다. 다음 예제에서 빨간색은 빼야 하는 인덱스, 파란색은 합을 구할 범위를 의미한다. (배열에 맨 앞에 0을 추가하여 범위가 1인 경우에도 같은 형식으로 처리할 수 있도록 하였다.) 먼저, 범위가 1인 경우 다음과 같이 유효한 값들을 구할 수 있다.

 

 

   해당 과정에서 위에서 정리한 1개일 때의 경우를 모두 구할 수 있다. 이번엔 범위 크기가 2인 경우를 확인해보자.

 

 

   범위 크기가 2인 경우에는 2개일 때와 같은 결과가 나오는 것을 확인할 수 있다. 이런 과정을 추가된 0을 제외한 배열의 크기까지 진행한 다음 나온 경우에 대한 수를 카운트한다. 이 과정을 통해 배열에 대해 만들 수 있는 부 배열과 각 부 배열이 나오는 수를 구할 수 있다.

 

   마지막 과정은 위의 방법을 이용해 구한 경우의 수를 이용해 T를 만들 수 있는 경우를 구하는 것이다. 즉, A 배열에서 선택한 부 배열의 값이 a라고 했을 때, B 배열에서 T - a라는 부 배열이 존재하는지 확인하고 존재하는 경우 T - a라는 부 배열의 경우의 수와 a 부 배열의 경우의 수를 곱한 값을 결과에 더해가면 된다. 두 배열의 부 배열이 다음과 같다고 하자.

 

• A 배열의 부 배열 : 1 - 1, 4 - 2, 5 - 1, 10 - 2
• B 배열의 부 배열 : 1 - 1, 2 - 2, 4 - 1, 7 - 2, 9 - 2

 

※ '숫자 - 숫자'의 형태는 '부 배열 - 해당 부 배열의 경우의 수'를 의미한다.

 

   이 경우 T가 8이라 가정하고 답을 구하면 다음과 같다.

 

• A 배열의 부 배열이 1인 경우 : T - 1 = 7, B 배열의 부 배열 7은 2개이고 A 배열의 부 배열 1은 1개이므로 총 2가지의 조합이 가능
• A 배열의 부 배열이 4인 경우 : T - 4 = 4, B 배열의 부 배열 4는 1개이고 A 배열의 부 배열 4는 2개이므로 총 2가지의 조합이 가능
• A 배열의 부 배열이 5인 경우 : T - 5 = 3, B 배열의 부 배열 3은 0개이므로 총 0가지 조합이 가능
• A 배열의 부 배열이 10인 경우 : T - 10 = -2, B 배열의 부 배열 -2는 0개이므로 총 0가지 조합이 가능

 

   최종적으로 총 4가지의 경우가 존재한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class 백준2143번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer token;

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        //n 배열을 이용해 만들 수 있는 조합(key)과 조합의 수(value)  
        Map<Long, Integer> nMap = makeMap();
        //m 배열을 이용해 만들 수 있는 조합(key)과 조합의 수(value)
        Map<Long, Integer> mMap = makeMap();
        long count = 0;

        //n과 m의 키들의 합으로 T를 만들 수 있는 경우의 수
        for (Long key : nMap.keySet())
            count += (long)nMap.get(key) * mMap.getOrDefault(T - key, 0);
        System.out.println(count);
    }

    //누적합을 이용해 조합을 저장하는 메서드
    public static Map<Long, Integer> makeMap() throws IOException {
        Map<Long, Integer> map = new HashMap<>();
        int len = Integer.parseInt(br.readLine());
        //모든 인덱스에 대해 형식을 맞춰주기위해 크기를 증가하여 배열 생성
        int[] arr = new int[len + 1];
        token = new StringTokenizer(br.readLine());

        //누적합 형태로 배열 초기화
        for (int i = 1; i <= len; i++)
            arr[i] = Integer.parseInt(token.nextToken()) + arr[i - 1];

        for (int i = 1; i <= len; i++) {
            for (int j = i; j <= len; j++) {
                //누적합 배열을 이용해 특정 구간의 합을 key로 사용
                Long key = (long)arr[j] - arr[j - i];
                //만들어진 key 값을 카운트
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
        }

        return map;
    }
}

//효율이 좋지 않은 코드