[BOJ] 1994번: 등차수열

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

일단 등차가 0인 경우는 먼저 처리를 해버리고, 중복되는 원소를 제거합니다. 그리고 수를 정렬하고 나면, 모든 i < j에 대해 num[i], num[j]를 초항으로 하는 등차수열의 길이를 구합니다. 이는 다음 항의 존재를 binary search로 파악할 수 있기 때문에 O(수열의 길이*lgN)에 수행할 수 있습니다. 그런데 문제는, 예를 들어 1 2 3 4 5 6 7 8 .... 1999 2000에 대해서 (1, 2)에 대해 2000까지 쭉 진행하고 (2, 3)에 대해 2000까지 쭉 진행하고 뭐 이런식으로 짜면 O(N^3*lgN)이 걸릴 수 있습니다. 이를 방지하기 위해 (1, 2)에서 3, 4, 5, ... 으로 뻗어갈 때 (2, 3), (3, 4), (4, 5) 등을 이미 확인했다고 마킹을 해둡니다.(코드 상의 isUsed가 그 역할을 수행) 그러면 최종적으로 O(N^2*lgN)에 해결할 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/1994.cpp