[백준/c++] 3273번: 두 수의 합

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

3273번: 두 수의 합

 

문제 요약

 

n개의 서로 다른 양의 정수 a1, ... , an으로 이루어진 수열

ai + aj = x를 만족하는 (ai, aj) 쌍의 수를 구하라.

 

 

범위

 

• 1 ≤ n ≤ 100000
• 1 ≤ x ≤ 2000000
• 1 ≤ ai ≤ 1000000

 

---

 

 

이 문제는 앞과 뒤를 가리키는 포인터를 두고, 해당 원소들의 합과 x를 비교한다. 

 

원소를 ⭐︎정렬하고 앞, 뒤에서 원소를 가리키며 해당 원소들의 합이 x와 같다면 count 해준다.

• 만약 x보다 크다면 뒤를 가리키는 r을 감소시킨다. 전의 합보다 더 작은 값을 만들 수 있다.
• 만약 x보다 작다면 앞을 가리키는 l을 증가시킨다. 전의 합보다 더 큰 값을 만들 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, x, arr[1000001], cnt = 0;

void input(){
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    cin >> x;
}

void solution(){
    int l = 0;
    int r = n-1;
    while(l<r){ //원소 하나 남은 것은 포함하지 않으므르
        int sum = arr[l] + arr[r];
        if(sum == x){ //쌍이 이루어지면
            cnt++;
            l++;
            r--;
        }else if(sum > x){
            r--;
        }else{
            l++;
        }
    }
    cout << cnt << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    sort(arr, arr+n);
    solution();
    return 0;
}

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!