★ solved.ac 난이도 : S3
(작성 시점 기준)
[문제 본문 링크]
3273번: 두 수의 합
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는
www.acmicpc.net
★ 풀이
단순 반복문으로도 답을 구할 수 있으나, O(n2) 시간 복잡도를 갖고 n이 최대 10만이므로 시간 초과가 발생할 것입니다.
이 문제는 투 포인터를 활용하여 해결할 수 있습니다.
먼저 주어진 수열을 정렬합니다.
그리고 양 끝 지점부터 탐색을 시작합니다. 탐색 도중 두 수의 합이 x와 같다면 ans를 1만큼 증가시킵니다.
다음으로 움직이는 방향을 정해야 합니다. 두 수의 합이 x보다 작으면 왼쪽 포인터를 증가시키고, 그렇지 않으면 오른쪽 포인터를 감소시킵니다.
이 과정을 왼쪽 포인터와 오른쪽 포인터가 만날 때까지 반복하고, ans의 값을 출력하면 됩니다.
[소스 코드 (C++98)]
공유 소스 보기
www.acmicpc.net
★ 틀린 점이 있다면 알려주세요~!