Boj 1253 좋다 c++

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

 

 

문제

 

길이가 N인 수열이 주어질 때, 각각의 수가 수열 내의 서로 다른 두수의 합으로 나타내어질 수 있는지 검사해야 한다.

수열의 길이는 최대 2000이다. 

(단, 두 수에는 자기 자신을 포함하지 않는다.)

 

풀이

 

두포인터 알고리즘을 사용하여 모든 수에 대한 검사를 수행한다.

이때, 자기 자신을 포함하지 않도록 주의.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

int arr[2001], N, ans;

int f(int t, int idx) {
    int s = 0, e = N-1, res;

    while(s < e) {
        res = arr[s] + arr[e];
        if(res == t) {
            if(s == idx){
                s++; continue;
            }
            if(e == idx) {
                e--; continue;
            }
            return 1;
        }
        if(res < t) {
            s++;
        }
        if(res > t) {
            e--;
        }
    }
    return 0;
}

int32_t main() {

    cin >> N;

    for(int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    sort(arr, arr+N);

    for(int i = 0; i < N; i++) {
        ans += f(arr[i], i);
    }
    cout << ans << "\n";
}