[Algorithm] 백준 - 합이 0 (3151번)

문제

[백준] 합이 0
(Olympiad > International Autumn Tournament in Informatics > 2011 > Group B (Juniors) 3번)

3151번: 합이 0

 

 

사용 알고리즘

- 이분탐색

- 투 포인터

- 정렬

해결방법

• 입력받은 학생들의 코딩실력 수열을 벡터 code_lv에 저장한 후 오름차순 정렬한다
• N명의 학생 중 코딩실력의 합이 0이되는 3명을 고르는 문제이므로 2중 for문을 돌며 벡터에서 2명의 학생을 고른후, 나머지 한 명은 이분탐색을 통해 고른다
  • ex) N : 10, code_lv {-6, -5, -4, -4, 0, 1, 2, 2, 3, 7}
  • [-6, -5] 일 때, 코드실력이 11인 학생을 2번 인덱스부터 이분탐색
  • [-6, -4] 일 때, 코드실력이 10인 학생을 3번 인덱스부터 이분탐색
  • . . .
  • [2, 3] 일 때, 코드실력이 -5인 학생을 9번 인덱스부터 이분탐색
• 이분탐색은 upper_bound와 lower_bound를 만들어 사용하였고, 두 함수의 리턴값의 차가 원하는 target값을 가진 학생 수가 된다 (오름차순 정렬을 해놨기 때문)

소스코드

사용언어 : c++

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

using namespace std; 

int N;
vector<int> code_lv;
long long res;

// 이진 탐색 : 특정 값의 첫 번째 등장 위치를 찾는 함수
int lower_bound(const vector<int>& vec, int start, int target) {
    int left = start;
    int right = vec.size();

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (vec[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

// 이진 탐색 : 특정 값의 마지막 등장 위치를 찾는 함수
int upper_bound(const vector<int>& vec, int start, int target) {
    int left = start;
    int right = vec.size();

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (vec[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

int main()
{
    cin >> N;

    for (int i=0; i<N; i++) {
        int num = 0;
        cin >> num;

        code_lv.push_back(num);
    }

    sort(code_lv.begin(), code_lv.end());

    for (int i = 0; i < N - 2; i++) {
        for (int j = i + 1; j < N - 1; j++) {
            int sum = code_lv[i] + code_lv[j];

            // 벡터 내 -sum 개수
            res += upper_bound(code_lv, j+1, -sum) - lower_bound(code_lv, j+1, -sum);
            /*
                c++ 제공 라이브러리를 사용할 수도 있다
                res += upper_bound(code_lv.begin()+j+1, code_lv.end(), -sum) - lower_bound(code_lv.begin()+j+1, code_lv.end(), -sum);
            */
        }
    }

    cout << res << endl;

    return 0;
}

lower_bound, upper_bound

lower_bound

* 찾으려는 키값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾는다

 

upper_bound

* 찾으려는 키값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함

* 다르게 표현하면, 찾으려는 키값이 마지막으로 등장하는 위치를 찾는다

 

(참고 블로그)

https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기

 

 

한줄평

처음엔 당연하게 조합문제라고 생각하여 백트래킹으로 nC3을 만드는 코드를 만들었는데 계속 시간초과가 발생하였다.;; 문제를 딱 봤을 때 이분탐색 문제인지 어떻게 판단해야할까. .