[백준 : 1253] 좋다 [C/C++] (투 포인터)

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

1253번: 좋다

 

문제에서 잘 확인해야 하는 조건

1. Ai가 너무 크니까 그냥 중첩 반복문으로는 안 될 것이라는 것을 알아야 한다.

2. Ai에 있는 절댓값 -> Ai가 음수일 수도 있으므로, Ai보다 작은 수의 범위 안에서만 투 포인터 알고리즘을 사용하는 것은 안된다.

3. 수의 위치가 다르면 값이 달라도 같은 수이다 -> 다른 수 두 개의 합으로 나타낼 수 있다 때문에 A[i]==A[start]orA[end]와 같다고 생각하면 안된다.

 

나는 2, 3번 때문에 왜 안되지.. 하고 있었다. 항상 문제의 조건을 잘 확인하자.

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

using namespace std;

int N;
vector<long long> A;
int ans;

int main()
{
    cin >> N;
    for(int i = 0; i<N; i++){
        long long t;
        cin >> t;
        A.push_back(t);
    }

    sort(A.begin(),A.end());

    for(int i = 0; i<N; i++){
        int start = 0;
        int end = N-1;
        while(start<end){
            if(start==i){
                start++;
                continue;
            }
            if(end==i){
                end--;
                continue;
            }
            if(A[start]+A[end]==A[i]){
                ans++;
                break;
            }
            if(A[start]+A[end]>A[i]){
                end--;
            }
            else{
                start++;
            }
        }
    }
    cout << ans;
}