[1253] 좋다

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

1253번: 좋다

<문제>

우선 2개를 고르며, 여기에서 O(N^2)을 소모한다. [0, n) 사이의 i, j에 대해서

i<j인 모든 (i, j)의 조합을 생성해주면 되겠다. 하나의 (i, j)에 대해 v[i] == v[j] + v[k]인 경우가 존재하는지

"v[i]-v[j]"의 lower_bound로 logN만에 판별할 수 있다.

 

동일한 수가 여러개 존재하는 경우를 정상적으로 탐색하기 위해선, 단순히 lower_bound()가 리턴한 인덱스만

확인하지 않고, 리턴한 인덱스부터 전부 탐색해주어야 한다. 그렇기에 3중for의 형태로 구현해주었다.

 

아래 코드에는 k<n이 있지만, idx==0, 모든 배열의 값이 같다 하더라도

i, j, k가 다르면 조기에 종료하기에 14라인의 for는 최대 3번만 수행되게 되므로

시간복잡도가 O(N^3)이 아닌 O(N^2logN)이 나오게된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
int main(void) {
    cin >> n;
    v.resize(n);
    int i, j, k, ans = 0;
    for (i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            int idx = lower_bound(v.begin(), v.end(), v[i] - v[j]) - v.begin();
            for (k = idx; k < n && v[k] == v[idx]; k++) {
                if (i != j && j != k && k != i && v[i] == v[j] + v[k]) {
                    ans++;
                    goto skipNext;
                }
            }
        }
    skipNext:;
    }
    cout << ans;
}