[C++]백준 - 2143번 문제

2143번: 두 배열의 합 (acmicpc.net)

2143번: 두 배열의 합

 

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(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

 

 

출력

---

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

 

 

 

---

 

생각해 볼 점

---

누적합 + 알파 문제입니다.

 

크게 2 가지 방법으로 풀 수 있을 것 같은데

 

1. 누적합을 구한 후 각 배열의 부 배열 조합을 구하여 투 포인터로 해결

2. 누적합을 구한 후 각 배열의 부 배열 조합을 구한 후 

두 배열의 모든 합의 조합을 구한 후 이분 탐색으로 해결 

 

시간적으로나 공간적으로나 1번 방법이 더 빠를 것이므로 1번 방법으로 풀겠습니다.

 

1. 각 배열의 누적합을 구합니다.

 

예시)

input_arr = {1, 3, 1, 2}

sum_arr = {1, 4, 5, 7}

 

2. 배열의 부 배열 조합을 구합니다.

 

예시)

input_arr = {1, 3, 1, 2}

sum_arr = {1, 4, 5, 7}

comb_arr = {1, 3, 1, 2, 4, 4, 3, 5, 6, 7}

 

3. 부 배열 조합을 정렬합니다.

 

예시)

comb_arr = {1, 1, 2, 3, 3, 4, 4, 5, 6, 7}

 

4. 두 부 배열 조합을 투 포인터 알고리즘으로 덧셈하여 T인 경우를 구합니다.

 

예시)

T = 5

comb_arr = {1, 1, 2, 3, 3, 4, 4, 5, 6, 7}

comb_arr2 = {1, 2, 3, 4, 5, 6}

 

* 주의 : 

만약 중복 숫자가 있으면 조합 가능한 갯수를 구해야 합니다.

 

자세한 내용은 코드를 참조하세요.

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int T;
    scanf("%d", &T);

    int N;
    scanf("%d", &N);

    vector<long long> arr_A(N + 1, 0);
    vector<long long> comb_A;
    
    //누적합
    for(int i = 0; i < N; i++)
    {
        scanf("%lld", &arr_A[i + 1]);
        arr_A[i + 1] += arr_A[i];
    }

    for(int i = 1; i < N + 1; i++)
    {
        for(int j = 0; j < i; j++)
            comb_A.emplace_back(arr_A[i] - arr_A[j]);
    }
    sort(comb_A.begin(), comb_A.end());
    
    int M;
    scanf("%d", &M);
    vector<long long> arr_B(M + 1, 0);
    vector<long long> comb_B;
    
    //누적합
    for(int i = 0; i < M; i++)
    {
        scanf("%lld", &arr_B[i + 1]);
        arr_B[i + 1] += arr_B[i];
    }
    for(int i = 1; i < M + 1; i++)
    {
        for(int j = 0; j < i; j++)
            comb_B.emplace_back(arr_B[i] - arr_B[j]);
    }
    sort(comb_B.begin(), comb_B.end());

    int index_A = 0;
    int size_A = comb_A.size();
    int index_B = comb_B.size() - 1;
    long long ans = 0;


    //투포인터
    while(index_A < size_A && 0 <= index_B)
    {
        long long summ = comb_A[index_A] + comb_B[index_B];

        //T인 경우를 모두 더함
        if(summ == T)
        {
            long long result_A = comb_A[index_A];
            long long result_B = comb_B[index_B];
            long long count_A = 0;
            long long count_B = 0;

            //같은 값이 아닐때까지 진행
            while(index_A < size_A && comb_A[index_A] == result_A)
            {
                index_A++;
                count_A++;
            }
            //같은 값이 아닐때까지 진행
            while(0 <= index_B && comb_B[index_B] == result_B)
            {
                index_B--;
                count_B++;
            }

            ans += count_A * count_B;
            continue;
        }
        if(summ < T)
            index_A++;
        else
            index_B--;

    }

    printf("%lld", ans);
    return 0;
}

 

그 외

---

조합 갯수가 놀랍게도.. int 범위를 넘어가기 때문에

 

72%에서 틀렸습니다가 뜬다면, ans를 long long으로 바꿔보시는 걸 추천합니다..