BOJ 1253번: 좋다

문제

문제 바로가기> BOJ 1253번: 좋다

1253번: 좋다

 

풀이

정렬 후 두 포인터를 이용하여 "좋은" 수를 찾을 수 있다.

* 서로 다른 두 수의 합은 해당 수를 사용해서 만들어지면 안된다!

 

#include<iostream>
#include<algorithm>
#define MAX 2001
using namespace std;

int N;
int num[MAX];

void input(){
    cin >> N;
    for(int i=0; i<N; i++) cin >> num[i];
}

void solution(){
    sort(num, num+N); // 정렬
    
    int ans = 0;
    for(int i=0; i<N; i++){
        int val = num[i];
        int l=0, r=N-1, sum;
        while(l < r){
            sum = num[l]+num[r];
            if(sum == val){
                if(l!=i && r!=i){
                    ans++;
                    break;
                }
                else if(l==i) l++;
                else if(r==i) r--;
            }
            else if(sum < val) l++;
            else r--;
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
}