[BOJ] 3273 두 수의 합 (C/C++)

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)

출력

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

---

투 포인터 문제에 익숙해지기 위해서 입문 문제를 풀어봤다. 이름처럼 점 두개를 잡고 조건에 따라서 점 두개를 이동해가면서 정답을 찾는 유형인 것 같다. 거창하게 새로운 알고리즘이 있거나 그런 것 같지는 않았다. 하지만 solved.ac 난이도가 실버3 정도임에도 알고리즘 분류에서 정렬과 투 포인터를 못 봤으면 아이디어를 떠올리는데 시간을 조금 썼을 것 같다.

 

이 문제는 입력된 배열을 정렬하고 양 끝에서 포인터를 이동해가면서 푸는 문제였다. 현재 두 포인터의 값을 더해서 x가 되는 경우엔 두 포인터를 가운데를 향해 한칸 이동시킨다. 합이 x보다 작은 경우엔 합이 더 커져야 하므로 왼쪽 포인터를 하나 증가시키고 반대의 경우 오른쪽 포인터를 한칸 이동시킨다. 

 

이때 입력에 n개의 다른 양의 정수가 아니라 중복되는 값이 들어올 수 있다면 단순히 이렇게 만해서는 안 풀릴 것 같았다. 그때는 아마 수열에서 각 수가 몇번씩 중복되는지 미리 세어놓고 수열에서는 중복을 제거해야 될 것 같다.

 

후기)

sort 함수를 사용하기 위해서 vector를 사용했다. resize를 사용해서 vector의 사이즈를 잡아놓은 다음에 push_back을 사용하지 않고 바로 값을 저장했다. push_back이 아무래도 바로 저장하는 것보다 시간이 오래 걸릴 것 같았는데, 둘 다 제출해보니 시간의 차이는 없었다. 대신 메모리가 500KB 정도 차이가 났는데 push_back을 사용하려면 임시 변수가 필요하긴 하다. 그런데 int 형 변수 하나 때문에 500KB이나 차이나지 않을 것 같은데 아마 오버헤드가 조금 있는 것 같다.