[백준 03151] 합이 0 [Java]

문제

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

---

풀이

N개의 수 중에서 3개의 숫자 합이 0인 경우의 수를 찾으면 된다.

N은 최대 10,000으로 완전 탐색을 하면 시간 초과가 발생한다.
N^2 탐색으로 두 수를 고른 후, 이분 탐색으로 나머지 수를 찾으면 된다.

두 수를 0부터 차례대로 완전 탐색을 하기 때문에 이분 탐색의 범위는 ( b + 1 ) ~ ( N - 1 ) 가 된다.

이 때, 두 수 a, b에 대해 c가 1개가 아닐 수 있다.

upper - lower로 동일한 c의 개수를 세주자.

---

소스코드

보기ttps://www.acmicpc.net/problem/3151

 

풀이

N개의 수 중에서 3개의 숫자 합이 0인 경우의 수를 찾으면 된다.

N은 최대 10,000으로 완전 탐색을 하면 시간 초과가 발생한다.

N^2 탐색으로 두 수를 고른 후, 이분 탐색으로 나머지 수를 찾으면 된다.

 

두 수를 0부터 차례대로 완전 탐색을 하기 때문에 이분 탐색의 범위는 ( b + 1 ) ~ ( N - 1 ) 가 된다.

 

이 때, 두 수 a, b에 대해 c가 1개가 아닐 수 있다.

upper - lower로 동일한 c의 개수를 세주자.

---

소스코드

보기