[알고리즘] C++ 백준 3151 합이 0

백준 3151

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

3151번: 합이 0

풀이 전 나의 생각

팀원의 코딩 실력 N개가 주어지는데 이 중 3개의 실력을 골라서 0이 될 수 있는

경우의 수를 모두 구해야한다.

 

조건

1 ≤ N ≤ 10000

-10000 ≤ Ai ≤ 10000

 

Solution

조건을 보면 N은 최대 10000개 까지 주어질 수 있다. 

일반적인 풀이법으로 생각해보면 요소 두개를 더해야 하니 2중 for문을 사용해야하고

더한 요소가 실제로 0을 만들 수 있는지 배열을 한번 더 탐색해야 하니 for문이 하나 더 늘어

최종적을 3중 for문이 만들어질 것이다. 그럼 10000 * 10000 * 10000 이라는 어마무시한 계산 횟수가

나오기 때문에 2중 for문 + 이분탐색으로 풀어야한다.

 

1. 정렬한 두 요소를 더한다.

int sum = coding_skill[i] + coding_skill[j];

두 요소를 미리 더해서 -를 해준다면 현재 찾고자 하는 목표 탐색 값을 얻을 수 있다.

ex) i(1) + j(2) = 3 ->  -3, -3은 3을 기준으로 0이 될 수 있는 값 

 

 

2. 현재 선택된 두 번째 요소의 다음부터 이분탐색을 진행한다.

int start = lower_bound(coding_skill + j + 1, coding_skill + N, -sum) - coding_skill;
int end = upper_bound(coding_skill + j + 1, coding_skill + N, -sum) - coding_skill;

ans += end - start;

예를 들어 주어진 N개의 배열 -1, -2, 3, 3, 5가 있고 선택된 첫번째 요소는 -1, 두번째 요소는 -2라고 가정하자.

 

두번 째 요소 배열 순서의 다음 순서인 2번째 부터 마지막 까지 이분탐색을 진행한다.

위에서 구했던 요소의 합 -1 + (-2)에 -를 해준 3의 lower_bound(3의 시작 위치) - upper_bound(3이 끝나는 다음 위치)를

구해주면 0을 만들 수 있는 모든 요소의 개수가 나오게된다.

 

예시 문제를 풀어보면 -1, -2를 더한 -3을 0으로 만들 수 있는 2개의 3을 구하는 방법은

3의 끝 다음 위치 4 에서 3의 시작 위치인 2를 빼면 우리가 구하고자 하는 -3을 0으로 만드는 3의 개수 2개를 구할 수 있다.

 

참고로 오름차순이기 때문에 선택된 두 요소 사이의 요소들은 탐색할 필요가 없다.

합쳐진 값은 선택된 두번째 요소보다 작을 수 없기 때문이다.

 

주의사항

최종 요소들의 개수를 담는 ans의 데이터 타입은 int로 설정하면 안된다.

모든 요소가 중복됐다고 가정하면 10000 * 10000을 탐색하면서 요소 9998, 9997, 9996....개를 넣어줄테니

10000 * 10000 * (9998 ~ 1) 의 횟수가 나오므로 int형의 약 21억의 공간은 바로 넘어버린다. 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int coding_skill[10001];

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

	int N;
	long ans = 0;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> coding_skill[i];
	}

	sort(coding_skill, coding_skill + N);

	for (int i = 0; i < N - 1; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			int sum = coding_skill[i] + coding_skill[j];

			int start = lower_bound(coding_skill + j + 1, coding_skill + N, -sum) - coding_skill;
			int end = upper_bound(coding_skill + j + 1, coding_skill + N, -sum) - coding_skill;

			ans += end - start;
		}
	}

	cout << ans;
}