[G4] 백준 3151번 합이 0 C++ 이분탐색, 정렬

리뷰

 

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

lower_bound, upper_bound를 사용하여 합이 0이 되는 모든 경우를 찾는 문제

 

 

전역 변수

• N : 배열의 최대값을 정의할 상수 변수
• n : 배열의 크기를 저장할 변수
• lst : 배열 정보를 저장할 배열

 

함수

없음

 

 

문제풀이

1. n을 입력 받고, n개의 요소를 입력 받아 lst배열에 저장해 준다.
2. sort함수를 통해 lst배열을 오름차순으로 정렬해 준다.
3. 변수 ans를 0으로 초기화 하고, 브루트포스 알고리즘을 개행해 준다.
4. 겹치지 않는 두 원소의 합을 변수 two에 저장해 준다.
5. 변수 ut에 upper_bound를 통해 두번째 원소 뒤 부터 배열의 끝 중 -two보다 큰 첫번째 이터레이터를 저장해 준다.
6. 변수 lt에 lower_bound를 통해 두번째 원소 뒤 부터 배열의 끝 중 -two이상인 첫번째 이터레이터를 저장해 준다.
7. ut - lt값을 ans에 더해준다. 브루트포싱이 끝난 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. lower_bound만 해주었다가 -two가 여러개인 경우를 처리해 주지 못해서 fail을 받았다.
2. lst배열을 정렬하지 않은 상태로 upper_bound, lower_bound를 사용하여 fail을 받았다.
3. lst배열을 정렬하고 upper_bound, lower_bound를 통해 -two의 개수를 잘 처리해 주어 AC를 받았다.

 

참고 사항

• upper_bound의 결과 - lower_bound의 결과를 하면 -two인 요소의 개수가 반환된다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e4;
int n;
int lst[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) cin >> lst[i];
	sort(lst, lst + n);

	long long ans = 0;
	for (int i = 0; i < n - 2; ++i) {
		for (int j = i + 1; j < n - 1; ++j) {
			int two = lst[i] + lst[j];
			auto ut = upper_bound(lst + j + 1, lst + n, -two);
			auto lt = lower_bound(lst + j + 1, lst + n, -two);
			ans += ut - lt;
		}
	}

	cout << ans;
}