[BOJ / c++] 13423 - Three Dots

링크

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

13423번: Three Dots

풀이

문제를 처음 보자마자 떠올린 풀이는 nC3으로 세 점을 뽑는 방법이였지만 시간복잡도 때문에 두 점을 뽑고 이진탐색으로 나머지 한 점이 찍혀있는지 확인하는 방법으로 풀었습니다.

하지만 위 방법으로 풀어도 시간초과가 떠서 이리저리 코드를 바꿔보면서 한참 해맸는데 (분명 시간복잡도 계산해 보면 시간 초과가 뜰리가 없는데...)

이진 탐색을 구현하는 함수 코드에서  call by reference가 아닌 call by value를 해버려서 시간초과가 난 것 같습니다 😂

bool binary_search(vector<int> v, int n) -> 잘못된 코드

bool binary_search(vector<int> & v, int n) -> 올바른 코드

 

코드

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

bool binary_search(vector<int> & v, int n) {
    int st = 0, ed = v.size() - 1;
    while (st <= ed) {
        int mid = (st + ed) / 2;
        if (v[mid] == n) return true;
        else if (v[mid] < n) {
            st = mid + 1;
        } else {
            ed = mid - 1;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
        }
        sort(v.begin(), v.end());
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (abs(v[i] + v[j]) % 2 == 0 && (binary_search(v, (v[i] + v[j]) / 2))) ans++;
            }
        }
        cout << ans << '\n';
    }
}