[BOJ 1253] 좋다

문제 링크 : https://www.acmicpc.net/problem/1253

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 A_i가 N개 주어진다. (|A_i| ≤ 1,000,000,000, A_i는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

제한

시간 제한	메모리 제한
2sec	256MB

힌트

3,4,5,6,7,8,9,10은 좋다.

---

풀이

이 문제는 리스트에 포함된 수 중 하나가 다른 두 수의 합으로 표현될 수 있는 ‘좋은 수’의 개수를 구하는 문제이다. $N$이 최대 $2\,000$으로 주어지므로, 모든 두 수의 조합을 살펴보는 $O(N^2)$ 기반의 접근이 가능하다. 특히 0이 포함된 경우 자기 자신을 합의 재료로 사용하는 실수를 하기 쉬운데, 개수 체크를 통해 이를 방지하는 것이 핵심이다.

효율적인 탐색을 위해 다음과 같은 과정을 수행한다:

• 정렬 및 데이터 구조화: 입력된 수들을 정렬한 뒤, 중복된 값은 값(v)과 해당 값이 등장한 횟수(cnt)를 묶어 별도의 구조체에 저장하여 탐색 효율을 높인다.
• 두 수의 조합 탐색: 이중 반복문을 통해 리스트에서 두 수를 선택한다. 이때 두 수가 같은 경우(해당 값의 개수가 2개 이상일 때)와 서로 다른 경우를 나누어 합을 구한다.
• 이분 탐색을 통한 존재 확인: 계산된 합이 리스트에 존재하는지 이분 탐색($O(\log N)$)으로 빠르게 확인한다.
• 예외 처리 (자기 자신 제외): ‘좋은 수’는 반드시 서로 다른 위치에 있는 두 수의 합이어야 한다. 만약 합의 결과물인 ‘좋은 수’가 선택한 두 수 중 하나와 값이 같다면, 리스트 내에 해당 값이 충분히 많이 존재하는지(예: 자기 자신 외에 다른 인스턴스가 있는지) 확인하여 ‘나 자신’을 재료로 쓰는 오류를 방지한다.

수의 절댓값이 최대 $1\,000\,000\,000$이므로 두 수의 합이 정수 범위를 유지하는지 유념하여 구현하며, 최종적으로 판별된 ‘좋은 수’들의 총 개수를 합산하여 출력한다.

소스코드

Github Link : Source Code

참고 알고리즘 : 이진 탐색