[백준] 5624 - 좋은 수

[문제]

---

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

[풀이]

---

나보다 앞에 있는 수 중에 아무거나 3개 더해서 나를 만들 수 있으면 좋은 수이다.
그냥 짜면 $O(N^3)$ 으로 안봐도 시간초과지만,
$-100,000 <= A[i] <= 100,000$ 이므로 배열로 수를 관리하여 시간복잡도를 줄일 수 있다.
또한 $N <= 5000$ 이고 시간제한이 1초여서 $O(N^2)$으로 충분히 풀 수 있다.

[코드]

---

n = int(input())
A = list(map(int, input().split()))
index = [[-1, -1] for _ in range(400_001)]
bias = 200_000

for i in range(n):
    for j in range(i, n):
        if index[A[i] + A[j] + bias][0] == -1:
            index[A[i] + A[j] + bias][0] = i
            index[A[i] + A[j] + bias][1] = j
        else:
            index[A[i] + A[j] + bias][0] = min(index[A[i] + A[j] + bias][0], i)
            index[A[i] + A[j] + bias][1] = min(index[A[i] + A[j] + bias][1], j)

ans = 0
for i in range(n):
    for j in range(i):
        if index[A[i] - A[j] + bias][0] == -1: continue
        if index[A[i] - A[j] + bias][0] >= i: continue
        if index[A[i] - A[j] + bias][1] >= i: continue
        ans+=1
        break
print(ans)