백준 2143 c++ "두 배열의 합" -PlusUltraCode-

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

[필자 사고]

이분 탐색 삘이 왔는데 어떻게 부분배열을 만들지가 고민이였다.

문제의 범위를 보자.. N이 1000밖에 안된다.

브루트포스로 모든 부분배열의 합을 구하면 백만개가 된다.

시간복잡도로 널널하다.

즉 이게 키 포인드라는 점이다.

 

각 브루트포스를 이용하여 배열의 모든 합들을 구한 뒤.

T-aSum[i] = findNum 을 통해 이진탐색으로 나머지 B도 탐색하면 문제 해결이다.

 

아래는 자세한 코드해설이다.

[코드 해설]

코드 해설

1. 입력 처리 단계
   • T: 두 배열의 부분합을 더했을 때 만들어야 하는 목표 합.
   • N, M: 각각 배열 A와 B의 크기.
   • 배열 A, B를 입력받아 각각 vector<int>로 저장한다.

---

1. 부분합 계산 단계
   • 배열 A의 부분합(aSum) 생성
     • A의 모든 구간에 대해 부분합을 구한다.
     • 예를 들어 A = [1, 3, 1]이라면
       • 가능한 부분합은 [1, 4, 5, 3, 4, 1] 과 같은 형태가 된다.
     • 이 모든 부분합을 aSum 벡터에 저장한다.
   • 배열 B의 부분합(bSum) 생성
     • B 배열도 동일하게 모든 구간의 합을 계산해 bSum에 저장한다.
     • 이렇게 하면 배열 A와 B 각각의 가능한 부분 구간 합들이 모두 모인다.

---

1. 정렬 단계
   • aSum과 bSum을 모두 오름차순으로 정렬한다.
   • 이후 이 정렬된 두 벡터를 이용해 이진 탐색(lower_bound, upper_bound)을 수행할 수 있게 된다.

---

1. 두 배열의 조합으로 T 만들기
   • aSum의 각 원소를 순회하며,
     • findNum = T - aSum[i] 값을 계산한다.
     • 즉, aSum[i] + bSum[j] = T를 만족시키는 bSum[j]를 찾아야 하므로
       bSum[j] = T - aSum[i] 인 값을 찾는다.
   • lower_bound와 upper_bound를 사용해
     bSum에서 findNum이 존재하는 구간의 시작과 끝 인덱스를 구한다.
     • lower_bound: findNum 이상이 처음 나타나는 위치
     • upper_bound: findNum 초과가 처음 나타나는 위치
   • 두 인덱스의 차이 (it2 - it1)은 findNum의 개수이므로,
     그 값을 결과 누적 변수 resultCount에 더한다.

---

1. 출력 단계
   • 모든 aSum[i]에 대해 가능한 조합을 계산한 후,
     최종적으로 구한 resultCount를 출력한다.
   • resultCount는 두 배열의 부분합 쌍 중 합이 T가 되는 경우의 수를 의미한다.

[소스 코드]

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

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    int N, M;
    cin >> T;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    cin >> M;
    vector<int> B(M);
    for (int i = 0; i < M; i++) cin >> B[i];

    vector<int> aSum;
    vector<int> bSum;

    // A 부분합
    for (int i = 0; i < N; i++) {
        int sum = 0;
        for (int j = i; j < N; j++) {
            sum += A[j];
            aSum.push_back(sum);
        }
    }

    // B 부분합
    for (int i = 0; i < M; i++) {
        int sum = 0;
        for (int j = i; j < M; j++) {
            sum += B[j];
            bSum.push_back(sum);
        }
    }

    sort(aSum.begin(), aSum.end());
    sort(bSum.begin(), bSum.end());

    long long resultCount = 0;
    for (int i = 0; i < aSum.size(); i++) {
        int findNum = T - aSum[i];
        auto it1 = lower_bound(bSum.begin(), bSum.end(), findNum);
        auto it2 = upper_bound(bSum.begin(), bSum.end(), findNum);
        resultCount += (it2 - it1);
    }

    cout << resultCount;
}