[ BOJ / C++ ] 3273번 두 수의 합

7532 단어 bojcppboj

이번 문제는 투 포인터 알고리즘을 활용해 푸는 문제였다.
투 포인터 알고리즘

  • 벡터를 오름차순으로 정렬해준다.
  • 두 개의 포인터를 벡터의 첫 인덱스와 끝 인덱스를 가리키게 한다.
  • 두 수의 합이 찾는 값과 같다면 cnt를 증가시켜주고 끝 인덱스를 감소시켜준다.
  • 두 수의 합이 찾는 값보다 크다면 끝 인덱스를 감소시켜준다.
  • 두 수의 합이 찾는 값보다 작다면 첫 인덱스를 증가시켜준다.
  • 첫 인덱스가 끝 인덱스와 같아질 때까지 반복한다.

Code

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

int n;
int a;
vector<int> arr;
int target;
int cnt=0;

void Input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>a;
        arr.push_back(a);
    }
    cin>>target;
}

void Solution(){
    int start=0;
    int end=n-1;
    sort(arr.begin(), arr.end());
    while(start<end){
        if(arr[start]+arr[end]==target){
            cnt++;
            end--;
        }
        else if(arr[start]+arr[end]>target){
            end--;
        }
        else{
            start++;
        }
    }
    cout<<cnt<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}

좋은 웹페이지 즐겨찾기