[백준][C++] 7453 합이 0인 네 정수

www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

 

 

 

알고리즘 종류

    - 이분탐색

 

 

 

사고 과정

    1. 합을 구하는 문제이므로 부분 합을 미리 구해 놓는다.

        1-1. 배열 A, B의 합을 미리 구한다.

        1-2. 배열 C, D의 합을 미리 구한다.

    2. 목표 값을 정해서 이분 탐색을 진행한다.

        2-1. 목표 값은 배열 AB(A와 B의 합이 저장된 배열)에서 하나씩 꺼내온다.

        2-2. 목표 값을 가지고 배열 CD에서 이분 탐색을 진행한다.

        2-3. 이분 탐색을 진행할 때, 중복 값이 나올 수 있다. 배열 AB에서 꺼내온 값이 -12라고 할 때, 우리는 배열 CD에서 12를 찾아야 한다. 그런데 12가 여러 개일 수 있다. 이를 처리할 수 있는 방법은 lower_bound와 upper_bound이다. lower_bound는 목표 값을 포함하여 처음 나온 값의 인덱스를 찾아주고, upper_bound는 목표 값을 초과하는 값이 처음 나온 인덱스를 찾아준다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<long long> A;
vector<long long> B;
vector<long long> C;
vector<long long> D;
vector<long long> AB;
vector<long long> CD;
 
int n;
long long a, b, c, d;
long long answer = 0;
 
 
int main(void){
    
    cin >> n;
    
    for(int i=0; i<n ;i++){
        cin >> a >> b >> c >> d;
        A.push_back(a);
        B.push_back(b);
        C.push_back(c);
        D.push_back(d);
    }
    
    // 배열 A와 B의 합, 배열 C와 D의 합   
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            AB.push_back(A[i] + B[j]);
            CD.push_back(C[i] + D[j]);
        }
    }
    
    // 배열 CD만 이분탐색을 진행하기 때문에 CD만 오름차순 정렬  
    sort(CD.begin(), CD.end());
    
    long long target;
    int left, right, mid;
    int idx1, idx2;
 
    for(int i=0; i<n*n; i++){
        
        // lower_bound : 목표 값 이상인 값이 처음 나오는 인덱스 
        target = -AB[i]; // -12 + 12 = 0이므로, -12에 -1을 곱해서 12를 찾는다. 
        left = 0;
        right = n*n;
        
        while(left < right){
            mid = (left + right) / 2;
            if(target <= CD[mid]) right = mid;
            else if(target > CD[mid]) left = mid + 1;
        }
        
        idx1 = left;
        
        // upper_bound : 목표 값 초과인 값이 처음 나오는 인덱스
        left = 0;
        right = n*n;
        
        while(left < right){
            mid = (left + right) / 2;
            if(target < CD[mid]) right = mid;
            else if(target >= CD[mid]) left = mid + 1;
        }
        
        idx2 = left;
        
        // 목표 값을 초과하는 값이 처음 나오는 인덱스 - 목표 값을 포함하여 처음 나오는 인덱스  
        answer += (long long)(idx2 - idx1);
    }
    
    cout << answer << endl;
}

 

 

 

시행착오

    - for문 4개를 사용하면 당연히 시간초과가 나오기 때문에 하지 않았다.

    - 이분탐색 또는 투포인터를 사용해 보고 싶어서 배열 A, B, C, D의 값에 id를 붙여서 1차원 배열에 모두 저장해 보았다. 하지만, 막상 방법이 떠오르지 않았다.

    - 합이 0이라면, 0을 기준으로 좌우로 최소 1개의 값이 포함되어야 한다. 단, 모두 0인 경우를 제외하고 말이다. 포인터를 4개 만들어서 해볼려고 했지만 움직이는 기준을 정하지 못했다.

    - 해결 방법을 참고하기로 했다. 사람들은 대단했다. 4개의 배열을 2개로 만들고, 이분탐색 또는 투포인터를 진행했다.

        * 배열 4개를 2개로 만드는 방법은 멋있었다. 목표는 합을 구하는 것이기 때문에, 부분 합을 미리 구해 놓는 것이었다. 즉, A[a] + B[b] + C[c] + D[d]를 구하는 것이 목표이기 때문에, A[a] + [b]를 미리 모두 구해 놓는 것이다.

        * 이분탐색에서 target을 정하는 방법을 한 번 더 배우게 되었다. 배열 AB와 CD가 만들어졌다. AB에서 target을 꺼내오고 CD에서 이분탐색으로 찾는다. 이전에 k번째 수 문제에서 감각에 추가로 더 배워서 기쁘다.

 

    - 다음에 이와 비슷한 문제가 나오면 다음과 같이 생각하면 될 것 같다. 

        1. 배열이 4개라서 복잡하네. 어차피 합을 구하는 것이 목표면 부분 합을 미리 구해 놓자.

        2. 부분 합 배열이 2개가 만들어 졌네. 그러면 이분탐색을 활용할 수 있을 것 같다.