7453 합이 0인 네 정수

www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int A, B, C, D;//합이 0이되는 것 의 수 뽑기
long long arr[40001][4];//입력으로 주어지는 배열
int N;// 배열의 크기
long long int ret;//결과 값
void init() {//초기 입력
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> arr[i][j];
		}
	}
}

void sumForArr() {//배열 합
	vector<long long>v1;
	vector<long long>v2;
	for (int a = 0; a < N; a++) {//미리 합 산출
		for (int b = 0; b < N; b++) {
			v1.push_back(arr[a][0] + arr[b][1]);
			v2.push_back(arr[a][2] + arr[b][3]);
		}
	}
	//sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	for (int i = 0; i < v1.size(); i++) {
		long long low = lower_bound(v2.begin(), v2.end(), -v1[i]) - v2.begin();
		long long high =upper_bound(v2.begin(), v2.end(), -v1[i]) - v2.begin();
		if (low == v1.size())continue;
		if (v1[i]+v2[low]==0) {
			cout << high << " " << low << endl;ret++;
		}
	}
}
int main(void) {
	init();
	sumForArr();
	cout << ret << endl;
	return 0;
}

//4
//1 2 3 - 5
//5 3 4 2
//- 3 - 4 2 1
//- 1 5 - 3 - 1

오름차순으로 무조건 정리를 해줘야하고

lower_bound 경우 찾는 값보다 같거나 큰 숫자 몇번째 배열에 나오는지 알려주는것이고,

upper_bound 경우 찾는 값을 초과하는 값이 몇번째 배열에 있는지 판단 

 

일단 여기서 보면 찾는 값이 -v[i] 인것은 1이 영이 되려면 -1 이되야하는것 처럼 반대되는 값을 찾기 위함

 

그리고 값을 찾으면 ++ 한개씩 증가하면 되지 않나 생각 할 수 있는데 

이 경우 그렇게 생각 하면 안되는것이 중복되는 숫자가 나올수 있습니다. 

1 2 6 6 7 이라는 배열이 있으면 

6번은 2, 3번 인덱스에 잇고 7은 4번 인덱스 인데 

이때 저대로 알고리즘을 돌리면 

low 2가 되고, high는 4가 됩니다. 

이경우 

6이 두개 이기 때문에 이전의 v1[i]가-6 이라면 2번이 카운터가 되어야 값이 맞습니다. 그렇기 때문에

 

high - low 를 해줘야 하는것이죠.

 

이해 되시죠?