728x90
1253번: 좋다
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
www.acmicpc.net
분석
투 포인터 이동원칙
- A[i] + A[j] > K : j--;
- A[i] + A[j] < K : i++;
- A[i] + A[j] == K : count++; 프로세스 종료
풀이
n = int(input())
list = list(map(int, input().split()))
list.sort()
cnt = 0
# 다른 두 수의 합인 수의 개수
for k in range(n):
val = list[k]
i = 0
j = n-1
while i < j: # 투 포인터 알고리즘
if list[i] + list[j] == val:
# 자기 자신을 좋은 수 만들기에 포함하면 안됨
if i != k and j != k:
cnt += 1
break
elif i == k:
i += 1
elif j == k:
j -= 1
elif list[i] + list[j] > val:
j -= 1
else:
i += 1
print(cnt)
728x90