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

문제링크 : https://www.acmicpc.net/problem/1253

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

    int N, result = 0;
    cin >> N;
    vector<int>v(N);
    for(int i=0; i<N; i++) 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++; continue;}
            if(r==i) {r--; continue;}

            if(v[i]==v[l]+v[r]) {result++; break;}
            else if(v[i] > v[l]+v[r]) l++;
            else r--;
        }
    }

    cout << result;

    return 0;
}

 

투 포인터를 활용한 문제이다.

투 포인터 사용을 위해 우선 입력받은 값들을 정렬시키고 시작한다.

 

해당 문제에서 탐색값은 현재 위치의 i값이 된다.

따라서 입력받은 0~N까지의 모든 i 값들을 타겟으로 탐색하며 v[i]=v[l]+v[r] 조건에 대해 부합한지 체크해준다.

자기 자신의 경우는 스킵해야하기에 l 또는 r이 i와 같다면 증가 및 감소시켜주고 스킵한다.

v[i]>v[l]+v[r]의 경우 목표값이 더 큰 케이스이기에 l 값을 증가시켜 더 큰 범위의 값을 탐색한다.

v[i] <v[l]+v[r]의 경우 목표값이 더 작은 케이스이기에 r 값을 감소시켜 더 작은 범위의 값을 탐색한다.

v[i] = v[l]+v[r]의 경우 목표 값이기에 카운팅 및 바로 while문을 종료시킨다.