[ 백준 / C++ ] 1253 : 좋다

[ 문제 ]

 

1253번: 좋다

 

[ 접근방법 ]

 

투 포인터 알고리즘을 활용하였다.

 

정렬된 배열의 시작과 끝에 포인터를 놓고 target과 비교해가며 포인터 위치를 조절한다.

 

target보다 크면 왼쪽 포인터를 늘리고, target보다 작으면 오른쪽 포인터를 줄인다.

 

시간 복잡도는 O(n)으로 작기에 문제를 풀기 충분하다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

ll n, ans;
vector<ll> v;

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

    cin >> n;
    for(int i = 0; i < n; i++){
        v.push_back(0);
        cin >> v[i];
    }
    sort(v.begin(), v.end());

    for(int i = 0; i < n; i++){
        int l = 0, r = n - 1;
        while(l < r){
            if(l == i)l++;
            else if(r == i)r--;
            else if(v[l] + v[r] < v[i])l++;
            else if(v[l] + v[r] > v[i])r--;
            else if(v[l] + v[r] == v[i]){
                ans++;
                break;
            }
        }
    }

    cout << ans;

    return 0;
}