[BOJ] 1253번_좋다_두 포인터 (C++)

[문제]

https://www.acmicpc.net/problem/1253

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 좋은 수 라고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하는 문제이다.
수의 위치가 다르면 값이 같아도 다른 수이다.

[사용 알고리즘]

두 포인터

[풀이 핵심]

• 오름차순으로 입력 받는다는 조건이 없으므로, 두 포인터를 사용하기 위해 algorithm헤더 파일의 sort()함수를 사용해서 오름차순으로 정렬해야한다.
• 입력받은 수들을 전부 벡터에 저장하여 0(start)부터 v.size()-1(end)까지 탐색한다. 탐색하는 방법은 v[start]와 v[end]를 더한 수가 v[i](만드려는 수)보다 작으면 start를 늘려 합을 더 크게 만들어주고, 더 크다면 end를 줄여 합을 더 작게 만들어 준다. 이렇게 탐색하면서 v[start]와 v[end]의 합이 v[i]가 되는지 판단해주면 된다.
• 좋은 수는 어떤 수가다른 수 두 개의 합으로 나타 낼 수 있는 수이기 때문에 v[start]와 v[end]의 합이 v[i]가 되었을 때 v[start], v[end] 둘다 v[i]와 다른 지 판단해야 한다. 숫자가 같아도 index가 다르면 다른 수 이기 때문에 숫자로 비교하는 것이 아니라 index로 비교해야한다. (실제로 v[start] != x && v[end] != x 이런식으로 if문의 조건을 달았다가 틀렸었음. x = v[start] + v[end]) 그리고 v[start], v[end]의 합이 v[i]이면서 v[start], v[end] 둘 중 하나가 v[i]와 같은 경우 v[start], v[end]말고 다른 수를 사용해서 v[i]를 만들 수 있는지 확인해야한다.

[코드]

//boj1253번_좋다_두 포인터

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

using namespace std;

int main() {
	int N;
	cin >> N;

	vector<int> v;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());

	int result = 0;

	for (int i = 0; i < v.size(); i++) {
		int x = v[i];

		int start = 0;
		int end = v.size() - 1;

		while (start < end) {
			int sum = v[start] + v[end];

			if (sum == x && (start != i && end != i)) {
				result++;
				break;
			}

			if (x < sum || end == i) {
				end--;
			}
			else if (x > sum || start == i) {
				start++;
			}
		}
	}

	cout << result;

	return 0;
}