[백준/C++] 3273번. 두 수의 합

[백준/C++] 3273번. 두 수의 합

1. 문제

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

2. 입력

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

3. 출력

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

4. 풀이

• 투 포인터 문제
• 두 개의 인덱스를 가지고 범위를 좁혀가면서 조건에 맞는 인덱스를 찾는다.
• 값을 모두 입력 받은 후에 먼저 배열을 정렬한다.
  • 양쪽에서 포인터를 좁혀가면서 탐색을 할 것이기 때문에 배열이 정렬되어 있어야한다.
• arr[start] + arr[end] 값과 target 값을 비교한다.
  • arr[start] + arr[end] == target: 원하는 값을 찾았기 때문에 결과를 추가하고 양쪽 인덱스를 좁힌다.
  • arr[start] + arr[end] < target: 원하는 값보다 작기 때문에 더 큰 값을 찾아야 한다. start를 늘려 값을 키운다.
  • arr[start] + arr[end] > target: 원하는 값보다 크기 때문에 더 작은 값을 찾아야 한다. end 줄여 값을 줄인다.

5. 처음 코드와 달라진 점

• while-loop 조건문을 start <= end 라고 작성해서 수정해주었다.
• start <= end라고 작성하면 target = 12 이고 arr[start==end] = 6 이면 실제로는 6이 하나밖에 없어도 순서쌍으로 나와서 개수가 더해진다.

6. 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, target;
vector<int> arr;

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

  cin >> n;

  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    arr.push_back(x);
  }

  cin >> target;

  sort(arr.begin(), arr.end());

  int start = 0, end = n-1;
  int answer = 0;
  while (start < end) {
    int sum = arr[start] + arr[end];
    if (sum == target) {
      answer++;
      start++;
      end--;
    }
    else if(sum < target) {
      start++;
    }
    else {
      end--;
    }
  }
  cout<<answer;
}