Three Dots (백준 13423)

안녕하세요. 오늘은 세개의 점을 만들 거예요.

문제

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

아이디어

이 문제는 O(N^3)으로는 풀리지 않습니다. 하지만 O(N^2)으로는 풀립니다. a,b를 고정시킨 다음에 이를 만족시키는 c의 값이 있는지 판별하는 방식으로 문제를 해결할 수 있습니다.

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll T, N, arr[1010] = { 0 }, i, a, b, c;

    cin >> T;
    while (T--)
    {
        cin >> N;
        for (i = 1; i <= N; i++) cin >> arr[i];
        sort(arr + 1, arr + N + 1);

        ll cnt = 0;
        for (a = 1; a <= N; a++)
        {
            for (b = a + 1; b <= N; b++)
            {
                c = lower_bound(arr + 1, arr + N + 1, arr[b] * 2 - arr[a]) - arr;
                if (c > N) continue;
                if (arr[c] == arr[b] * 2 - arr[a]) cnt++;
            }
        }
        cout << cnt << "\n";
    }
}

감사합니다.