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

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

3151번: 합이 0

 

 

[ 문제풀이 ]

 

1. 입력받은 수들을 arr 배열에 저장하고, 오름차순으로 정렬합니다.

 

2. arr를 0부터 N-2까지 for문을 통해 돌면서 start = i+1, end = N-1로 시작하여

 - arr[ i ] + arr[ start ] + arr[ end ]의 값이 0보다 크다면 end--

 - arr[ i ] + arr[ start ] + arr[ end ]의 값이 0보다 작다면 start++

 - 0이라면 분기를 나누어 ans에 값을 더해줍니다.

이때, arr[ i ]의 값이 0보다 크다면 세 수의 합이 0이 될 수 없으므로 반복문을 종료해줍니다.

 

3. 2에서 sum이 0일 때,

 - start와 end의 값이 같다면 end - start + 1개 중 두 개를 뽑는 경우의 수를 ans에 더해주고

 - arr[ start ] == arr[ start + 1]일 때 left++

 - arr[ end ] == arr [ end - 1 ]과 같다면 right++

마지막에 ans에 left * right 를 더해줍니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
int N;
int arr[10000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    sort(arr, arr + N);
 
    ll ans = 0;
 
    for (int i = 0; i < N - 2; i++) {
        int start = i + 1;
        int end = N - 1;
 
        if (arr[i] > 0) break;
 
        while (start < end) {
            int left = 1;
            int right = 1;
            int sum = arr[i] + arr[start] + arr[end];
            if (sum == 0) {
                if (arr[start] == arr[end]) {
                    int temp = end - start;
                    ans += (1LL * temp + 1) * (1LL * temp) / 2;
                    break;
                }
                while (arr[start] == arr[start + 1]) {
                    start++;
                    left++;
                }
                while (arr[end] == arr[end - 1]) {
                    end--;
                    right++;
                }
 
                ans += 1LL * left * right;
                start++;
                end--;
            }
            else if (sum > 0) {
                end--;
            }
            else {
                start++;
            }
        }
    }
 
    cout << ans;
}