[C++] 백준 3273 - 두 수의 합

문제 - 두 수의 합 (Silver 3)

[백준 3273] https://www.acmicpc.net/problem/3273

풀이 전략

• 투 포인터를 사용해서 A[i]+A[j]=x를 만족하는 수를 찾는다.
• 순서 상관없이 두 수의 합만 x와 일치하면 되기 때문에 오름차순으로 정렬한 뒤 start 포인터는 0번 index에서, end 포인터는 N-1번 index에서 시작해서 움직인다.
• x와 같을 때, 작을 때, 클 때의 경우를 나눠서 포인터를 움직인다.

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

    int N;
    cin>>N;

    vector<int>A(N,0);
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    int target;
    cin>>target;

    int start=0, end=N-1, count=0;
    sort(A.begin(),A.end()); // 오름차순 정렬

    while(start<end){
        if(A[start]+A[end]==target){
            count++;
            end--;
        }
        /* 목표 값과 같으면 count를 늘리고 end 포인터를 한 칸 앞으로 당김
        그래야 합이 작아져서 else if 조건문으로 넘어간 뒤, 또 다른 경우를
        찾을 수 있기 때문에 */
        else if(A[start]+A[end]>target){
            end--;
        }
        // 합이 크면 합을 작게 만들어주기 위해 end 포인터를 앞으로 당김
        else if(A[start]+A[end]<target){
            start++;
        }
        // 합이 작으면 합을 크게 만들어주기 위해 start 포인터를 뒤로 밀음
    }
    cout<<count<<'\n';
    return 0;
}

결과