[백준] 3151번 - 합이 0 (C++) 문제 및 풀이

문제) 백준 - 이분 탐색 - 합이 0

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

3151번: 합이 0

 

N이 최대 10000이므로 O(N*N*logN)의 시간 복잡도로 해결할 수 있었습니다. 두 개의 숫자(이중 반복문)를 선택 후, 이분 탐색을 통해 나머지 숫자들 중 0이 되는 숫자의 개수를 세어주면 해결할 수 있습니다.

 

C++ 소스코드)

	sort(A, A + N);
	// O(N)
	for (int i = 0; i < N - 2; ++i) {
	//O(N)
	for (int j = i + 1; j < N - 1; ++j) {
	// O(logN)
	int total = A[i] + A[j];
	ans += (upper_bound(A + j + 1, A + N, (-1) * total) - lower_bound(A + j + 1, A + N, (-1) * total));
	}
	}

view raw 3151.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/3151_%ED%95%A9%EC%9D%B4%200.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions