백준 3273번: 두 수의 합 (C++)

문제

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

• 입력
  • 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)
• 출력
  • 문제의 조건을 만족하는 쌍의 개수를 출력한다.

코드

#include <iostream>
using namespace std;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int num[100001] = {};
    bool isExist[2000001];

    int n, x;

    cin >> n;

    for (int i = 0; i < n; i++) cin >> num[i];

    cin >> x;

    int cnt = 0;
    for (int i = 0; i < n; i++){
        if(x - num[i] > 0 && isExist[x - num[i]]) cnt++;
        isExist[num[i]] = true;
    }

    cout << cnt << "\n";
}

접근 및 풀이

자연수 x가 주어졌을 때, 수열 내 숫자 두 개를 더했을 때 x가 되는 쌍이 몇 개나 있는지 알아보는 문제이다. 처음 문제를 보았을 때 int 배열 두 개를 냅다 만들었다가 segmentation fault를 보고 다시 풀었다…

내가 푼 방법은 요약하자면 다음과 같다.

먼저 순서대로 들어오는 수열을 넣을 int형 배열 num을 만들었다. 최대 들어올 수 있는 크기가 100000이기 때문에 100001의 크기로 만들었다. 그리고 나서 수열이 담긴 배열을 순회하면서 해당 숫자의 쌍이 존재하는지 확인할 수 있는 bool형 배열 isExist를 만들었다. 이 또한 x의 크기가 2000000인 것을 감안하여 2000001의 크기로 만들었다.

쌍을 확인하는 for문에서는

1. 각 수열을 돌며 x에서 해당 숫자를 빼서 0보다 큰지 확인한다. 수열에 들어간 숫자는 모두 양의 정수이기 때문에 x보다 큰 수는 쌍을 만들 수 없기 때문이다.
2. 또한 해당 숫자와 쌍을 만들 수 있는 숫자가 앞에 등장했는지 확인한다.

두 경우 모두에 해당하면 쌍의 개수를 담는 변수인 cnt에 1을 더한다.

그 다음 isExist 배열에 해당 숫자가 존재한다는 표시를 해준다.

수열의 첫 번째 숫자가 12이고, x가 13이라면 해당 숫자의 쌍은 1이다. 1은 양의 정수이지만 존재하지 않기 때문에 count해주지 않는다. 그리고 나서 12가 존재한다는 표시를 해준다.

수열의 다음 숫자가 9이고, x가 13이라면 해당 숫자의 쌍은 3이다. 3은 양의 정수이지만 존재하지 않기 때문에 count해주지 않는다. 그리고 나서 9가 존재한다는 표시를 해준다.

수열의 다음 숫자가 1이고, x가 13이라면 해당 숫자의 쌍은 12이다. 12은 양의 정수이고 존재하기 때문에 count해준다. 그리고 나서 12가 존재한다는 표시를 해준다.

수열의 다음 숫자가 14이고, x가 13이라면 해당 숫자의 쌍은 -1이다. -1은 음의 정수이기 때문에 존재할 수 없다. 그리고 나서 14가 존재한다는 표시는 해준다.

x의 쌍이 음의 정수라면 if문을 한번 더 돌려서 존재한다는 표시를 아예 안 해주는 게 좋을지 그냥 이대로 둬도 상관없을진 모르겠다. 더 좋은 방법이 있으면 알려주세요…?