[백준] 두수의 합

문제 링크: https://www.acmicpc.net/problem/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)

출력

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

문제 이해

입력 받은 숫자중 두 수의 합이 x와 같은 개수를 찾아라.

문제 접근

1. 입력을 받아서 sort하기
2. 두 수의 조합들을 찾기

1.c++ alogrithm header에 있는 sort를 사용하여 sort를 하였다
2.한 인덱스는 처음부터 다른 인덱스는 끝에서부터 검사하도록 했다. 두 인덱스가 만나면 멈추게했다.
그리고 만약 두 인덱스가 접근한 값의 합이 x와 같다면, 처음부터 시작한 index는 +1를 해주고, 끝에서 시작에 인덱스는 -1을 해주었다.
x보다 두수의 합이 크다면, 끝에서 시작한 인덱스만 -1해주었고, x보다 두수의 합이 작다면, 앞에서 시작한 인덱스만 +1해주었다.

코드 구현(c++)

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

using namespace std;

int N,x;
vector<int> nums;
int cnt = 0;

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

    cin >> N;
    int tmp;
    for(int i = 0 ; i < N ; i++){
        cin >> tmp;
        nums.push_back(tmp);
    }
    cin >> x;
    sort(nums.begin(),nums.end());
    int start = 0;
    int end = N - 1;
    while(1){
        if(start >= end) break;
        tmp = nums[start] + nums[end];
        if(tmp == x){
            start++;
            end--;
            cnt++;
        }
        else if(tmp > x) end--;
        else start++;
    }

    cout << cnt;
}

평가

처음에 dfs를 사용하여 문제를 풀려고 했지만, 시간초과가 일어났다. dfs의 시간이 걸리는 정도가 어느정도인지 파악하고 풀어야겠다. 그래서 이 문제는 sort를 해서 접근하는 방법으로 했다. 생각하는게 어려웠지만, 구현하는 것은 쉽게하였다.