[백준] 3152번 : 합이 0 (C++)

3152번 : 합이 0

---

문제)

Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다.

 

Elly는 그녀가 가르칠 수 있는 모든 학생들의 코딩 실력을 알고 있다. 각각의 코딩 실력 Ai는 -10000부터 10000 사이의 정수로 표시되어 있다. 그녀는 팀워크와 코딩 실력이 모두 적절한 팀을 만들기 위해, 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 이러한 조건 하에, 그녀가 대회에 출전할 수 있는 팀을 얼마나 많이 만들 수 있는지를 계산하여라.

 

N명의 학생들의 코딩 실력 Ai가 -10000부터 10000사이의 정수로 주어질 때, 합이 0이 되는 3인조를 만들 수 있는 경우의 수를 구하여라.

 

 

 

입력 :

입력은 표준 입력으로 주어진다.

첫 번째 줄에 학생의 수 N이 입력된다. 두 번째 줄에 N개의 그녀가 가르칠 학생들의 코딩 실력인 Ai가 주어진다.

 

 

 

출력 :

표준 출력으로 그녀가 고를 수 있는 팀의 수를 하나의 정수로 출력한다.

 

 

 

 

 

풀이)

 

// 3151. 합이 0
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
vector<int> vec;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    vec.resize(n);
    for (int& ele : vec) cin >> ele;
 
    // 정렬
    sort(vec.begin(), vec.end());
 
    long long cnt = 0;
 
    // 두개의 수를 고른다.
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
 
            // 두개의 수가 골라진 상황에서, 
            // 이진탐색을 이용하여 0이 만들어지는 수의 개수를 구한다.
            int s = i + 1;
            int e = j - 1;
 
            int left = 0, right = 0;
            
            while (s <= e)
            {
                int mid = (s + e) / 2;
 
                if (vec[i] + vec[j] + vec[mid] == 0)
                {
                    right = mid;
                    s = mid + 1;
                }
                else if (vec[i] + vec[j] + vec[mid] < 0)
                {
                    s = mid + 1;
                }
                else e = mid - 1;
            }
 
            s = i + 1;
            e = j - 1;
 
            while (s <= e)
            {
                int mid = (s + e) / 2;
 
                if (vec[i] + vec[j] + vec[mid] == 0)
                {
                    left = mid;
                    e = mid - 1;
                }
                else if (vec[i] + vec[j] + vec[mid] > 0)
                {
                    e = mid - 1;
                }
                else s = mid + 1;
            }
 
            if (right >= left && right != 0 && left != 0)
            {
                cnt += right - left + 1;
            }
        }
    }
 
    cout << cnt;
 
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/3151 

3151번: 합이 0