[C++]백준 - 3273번 문제

3273번: 두 수의 합 (acmicpc.net)

3273번: 두 수의 합

 

3273번 : 두 수의 합

---

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

 

 

출력

---

문제의 조건을 만족하는 쌍의 개수를 출력한다.

 

 

---

 

생각해 볼 점

---

정렬 후, 투포인터를 통해 쌍을 구할 수 있습니다.

 

정렬이 되었다면, 가장 앞쪽에는 제일 작은 수, 가장 뒤쪽에는 제일 큰 수가 있을 것입니다.

 

투포인터의 Left = 0, Right = N-1로 두고,

 

Left의 위치 + Right의 위치를 구하여 X값과 비교합니다.

 

예를 들어, 입력이 {5, 2, 3, 6, 8, 3, 7}이고, 구하려는 X가 12라면

 

1. 정렬 실행

 

{2, 3, 5, 6, 7, 8}

 

2. Left와 Right 포인터 설정

 

{2, 3, 5, 6, 7, 8}

L = 0

R = 5

 

3.  두 값을 더한 값을 X와 비교하여 X보다 작다면, L을 1 증가시키고 X보다 크다면 R을 1 감소시킴

 

{2, 3, 5, 6, 7, 8}

 

2 + 8 = 10,

10 < X(12)

-> L ++

 

4. 두 값을 더한 값이 X와 같다면, L + 1, R - 1을 수행하고, 결과값을 1 증가시킴

 

 

위의 과정을 L이 R보다 작은 동안 반복하여 수행하면 됩니다.

 

 

코드

---

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

int main() 
{
	int N, X;
	scanf("%d", &N);
	
	vector<int> v;
	for(int i = 0; i < N; i++)
	{
	    int input;
	    scanf("%d", &input);
	    v.push_back(input);
	}
	sort(v.begin(), v.end());
	
	scanf("%d", &X);
	
	//투포인터
	int result = 0;
    int l = 0;
    int r = N - 1;
    while(l < r)
    {
        int lr = v[l] + v[r];
        if(lr < X) l++;
        else if(lr > X) r--;
        else 
        {
            l++;
            r--;
            result++;
        }
    }
	
	printf("%d", result);
	return 0;
}

 

그 외

---