[백준] 1253번 좋다 (C++)

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

 

 

이 문제는 N개의 정수가 주어졌을때 각 요소가 나열된 수중 2개의 합으로 나타낼 수 있으면 좋은 수이며

좋은 수의 개수를 출력하는 문제이다.

 

개수가 최대 2000개이므로 시간복잡도를 최대한으로 줄이기 위해서 원소 하나를 잡고 투 포인터 알고리즘을 사용하여
다른 수로 나타낼 수 있는지 확인하였다 이렇게 되면 O(N^2)으로 시간을 최대한으로 효율적으로 풀 수 있다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N;

bool check(int val, vector<int> &v, int idx) {
    int left = 0;
    int right = N-1;

    while(left < right) {
        if(left == idx) {left++; continue;}
        if(right == idx) {right--; continue;}

        int stand = v[left] + v[right];

        if(stand == val) {
            return true;
        }

        if(stand < val) {
            left++;
        }
        else right--;
    }

    return false;
}

void solve(vector<int> &arr) {
    int cnt = 0;
    sort(arr.begin(), arr.end());

    for(int i = 0; i < N; i++) {
        if(check(arr[i], arr, i)) cnt++;
    }

    cout << cnt;
}

void input() {
    cin >> N;

    vector<int> v(N, 0);

    for(auto &it : v) {
        cin >> it;
    }

    solve(v);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}