[백준 13423] Three Dots

 

점 a, b, c 를 완적탐색으로 하면  O(n^3)으로 시간초과가 나게 된다.

 

점 a, b 를 고르고 이분탐색으로 c를 찾으면 O(n^2 log n)으로 AC를 맞을 수 있지만

O(n^2)의 방법으로 풀어보겠다.

 

점 a, b 를 정하고 b-a와 같은 값 c를 b < k < n 에서 찾는다.

k == n-1 일때까지 모두 탐색했다면 b를 오른쪽 점으로 한칸 옮겨서 반복 수행한다.

a점도 마찬가지로 b점이 b == n-2 이면 오른쪽으로 움직인다.

 

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int t = Integer.parseInt(br.readLine());
        while(t-->0) {
            int n = Integer.parseInt(br.readLine());
            int a[] = new int[n];
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++) a[i] = Integer.parseInt(st.nextToken());
            
            int cnt = 0;
            Arrays.sort(a);
            for(int i=0; i<n-2; i++) {
                int k = i+2;
                for(int j=i+1; j<n-1; j++) {
                    int ba = a[j] - a[i];
                    
                    while(k < n && a[k] - a[j] < ba) {
                        k++;
                    }
                    
                    if(k == n) break;
                    
                    if(a[k] - a[j] == ba) cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
}