백준 7453 합이0인네정수 c++ // 이분탐색 갯수세기는 ub-lb

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

7453번: 합이 0인 네 정수

1. 의사코드

1. a+b의 결과를 답은 배열v1생성

2. c+d의 결과를 담은 배열 v2생성

3. v2에서 -v1을 이분탐색후 UB-LB == 해당순서쌍의갯수를 ret에 더해나감

 

2.시행착오

위의 3번과정에서 단순히

binary_search가 참이면 ret+1을 함

문제 : v1 : 2 , v2 : -2 -2 -2 일때,

순서쌍은(0,0,2,2) (0,0,2,3) (0,0,2,4) 총 3쌍이 더해져야하는데

1개만 카운트 되므로 오답임!

 

3.정답코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll ret;
int n;
vector<ll> a,b,c,d,v1,v2;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i=0;i<n;++i){
		ll q,w,e,r;
		cin >> q>>w>>e>>r;
		a.push_back(q);
		b.push_back(w);
		c.push_back(e);
		d.push_back(r);
	}

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());
	sort(d.begin(), d.end());
	
	//1. v1배열에 a와+b를 조합한 숫자들을넣음
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			v1.push_back(a[i] + b[j]);
		}
	}
	//2.c배열에 c+d 숫자들넣기
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			v2.push_back(c[i] +d[j]);
		}
	}

	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());

	for (int i = 0; i < v1.size(); ++i) {
		int ub = upper_bound(v2.begin(), v2.end(), -v1[i]) - v2.begin();
		int lb = lower_bound(v2.begin(), v2.end(), -v1[i]) - v2.begin();
		ret += ub - lb;
	}


	cout << ret;
	return 0;
}