이번 문제는 백준의 골드 4 문제 좋다 문제이다.
문제를 차근차근 한 번 읽어보도록 하자.
주어진 수 내에서 두 수를 뽑아 다른 수를 만들 수 있는 경우를 세어달라고 한다.
최대로 주어지는 수의 개수는 2000개 까지 주어지며,
각 수는 최대 10억의 범위를 가지며, 정수이기 때문에 음수도 가질 수 있다.
가장 먼저 드는 생각은 그냥 for문으로 탐색하는 것이었다.
그럼 당연히 이중 for문을 사용하게 될 것인데, 시간 복잡도는?
2000개의 수를 O(N^2)으로 탐색하는데에는 4,000,000회가 소요된다.
생각해보면, 시간초과가 날 것 같지는 않은 횟수이다.
하지만 골드 4 문제인데 이게 맞는 풀이는 아닐거라는 생각이 든다.
어떤 방식으로 짧은 시간 내에 해결할 수 있을까?
투 포인터
빠르게 두 수의 합을 조사할 수 있는 방법을 생각하다보니, 투포인터가 떠올랐다.
투 포인터의 시간 복잡도는 O(N)으로 일반 탐색보다 훨씬 단순하다.
투 포인터 방식을 사용하기 위해서는 먼저 정렬을 해야 할 것 같다.
두 수의 합을 기준으로 생각하기 때문에, 정렬을 해야 편할 것 같다.
이제 포인터를 어떻게 훑을 것인지가 핵심이다.
먼저, 앞에서부터 뒤로 훑는다고 생각해보자.
과연 모든 수의 조합을 확인할 수 있을까?
불가능하다. 앞에서 뒤로 훑기만 해서는 모든 조합을 확인할 수 없다.
투 포인터 + 이분 탐색
그럼 앞에서 뒤로 훑는 것이 아닌, 앞과 뒤에서 조이는 건 어떨까?
주어진 수열에서 수를 하나 잡고, 앞과 뒤에서 조이며 합해보는 것이다.
마치 이분탐색을 진행하는 원리와 동일하다.
이렇게 앞 뒤가 같아질 때까지 진행하면, 모든 조합의 합을 구할 수 있다.
또한, 각 포인터가 본인을 지정할 수는 없기 때문에 잘 조절해야 한다.
실제 구현 코드는 아래와 같다.
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
ll num = 0, answer = 0;
ll number_list[2000];
int main() {
cin >> num;
for (int i = 0; i < num; i++)
cin >> number_list[i];
// 투 포인터로 긁으면 모든 수 표현 가능
// 왜? 핵심은 모든 수를 표현해야 하는게 아님.
sort(number_list, number_list + num);
for (int i = 0; i < num; i++) {
ll target = number_list[i];
int left = 0, right = num - 1;
while (left < right) {
int partial_sum = number_list[left] + number_list[right];
if (partial_sum < target)
left++;
else if (partial_sum > target)
right--;
else if (partial_sum == target) {
if (left != i && right != i) {
answer++;
break;
// 본인은 결과에 포함시킬 수 없음
}
else if (left == i)
left++;
else if (right == i)
right--;
// 본인이 등장했으면 지나쳐야 한다.
}
}
}
cout << answer;
return 0;
}두 가지 개념이 결합된 문제였다.
이런 문제가 풀이를 떠올리기 꽤 힘든 것 같다.
복합 개념이 들어간 문제와 구현 문제를 더 열심히 보도록 하자.