백준 2143 두 배열의 합 쉬운 풀이(C++/CPP)

문제링크 : https://www.acmicpc.net/problem/2143

아이디어

• A,B의 각각 부배열을 구하는 방법
  • 애초에 들어올떄 해당 인덱스까지의 합을 받아옴
  • 각 인덱스 순회하면서 모든 경우의 수를 구함
  • O(N^2)
• A,B 각각 더해서 값을 구할경우 : O(N^2 * N^2) = O(N^4) = 1e12 > 시간초과
• A의 값을 고정한다음에, 더해서 0이되는 값을 B에서 이진탐색으로 찾음
• B 배열에서 같은 값이 여러개일경우에??
  • 이진탐색을 lower bound, upper bound 같이 수행해서 차이만큼 빼기

시간복잡도 계산

• B 정렬 : N^2lgN^2
• A순회하면서 이진탐색 :N^2 lgN^2
• O( N^2lgN^2 + N^2lgN^2) = O( N^2lgN^2) = 1e6 * lg(1e6) = 1e6 * 20 = 2e7

인트 계산

• 더해서 최악의 캐이스 : N * 1e6 * 2 = 1e3 * 1e6 * 2 = 2e9 > INT 가능
  • 결과값 : 1e6개 * 1e6개 = 1e12개 >> ll 사용
    

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
int sumA[1010];
int sumB[1010];
int partA[1000010];
int partB[1000010];
 
int binsearchlower(int st, int en, int target) {
    if(st==en) {
        if(partB[st] == target) return st;
        return -1;
    }
 
    int mid = (st+en)/2;
    if(partB[mid] < target) return binsearchlower(mid+1, en, target);
    else return binsearchlower(st, mid, target);
}
 
int binsearchupper(int st, int en, int target) {
    if(st==en) {
        if(partB[st] == target) return st;
        return -1;
    }
 
    int mid = (st+en+1)/2;
    if(partB[mid] <= target) return binsearchupper(mid, en, target);
    else return binsearchupper(st, mid-1, target);
}
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T; cin >> T;
    int N; cin >> N;
    cin >> sumA[0];
    partA[0] = sumA[0];
    for(int i=1; i<N; i++) {
        cin >> sumA[i];
        // 이전값이랑 합함
        sumA[i] += sumA[i-1];
    }
 
    int cntA=0;
    for(int j=0; j<N; j++) {
        partA[cntA] = sumA[j];
        cntA++;
        for(int i=0; i<j; i++) {
            partA[cntA] = sumA[j] - sumA[i];
            cntA++;
        }
    }
 
 
    int M; cin >> M;
    cin >> sumB[0];
    partB[0] = sumA[0];
    for(int i=1; i<M; i++) {
        cin >> sumB[i];
        // 이전값이랑 합함
        sumB[i] += sumB[i-1];
    }
 
    int cntB=0;
    for(int j=0; j<M; j++) {
        partB[cntB] = sumB[j];
        cntB++;
        for(int i=0; i<j; i++) {
            partB[cntB] = sumB[j] - sumB[i];
            cntB++;
        }
    }
 
    sort(partB, partB+cntB);
 
    ll rs=0;
    for(int i=0; i<cntA; i++) {
        int tar = T - partA[i];
        // 같은 값을 나오는걸 어떻게 할까 >> lower, upper 둘다 구해서 인덱스 더하자
        int st = binsearchlower(0,cntB-1,tar);
        if(st != -1) {
            int en =binsearchupper(0,cntB-1,tar);
            rs += (en-st+1);
        }
    }
 
    cout << rs << '\n';
    
    return 0;
 
}
 
 
 

문제유형

• 이진탐색 - 모든케이스에서 이진탐색

비슷한 문제

• https://www.acmicpc.net/problem/1300
• https://www.acmicpc.net/problem/1939
• https://www.acmicpc.net/problem/8983
• https://www.acmicpc.net/problem/3020
• https://programmers.co.kr/learn/courses/30/lessons/43238
• https://www.acmicpc.net/problem/2143