백준 1253 c++ "좋다" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 주어진 수열에서 특정 수가 수열 내 다른 두 수의 합으로 표현될 수 있는지를 찾는 것이다. 이를 해결하기 위해 다음 절차를 따른다:

1. 투 포인터 알고리즘 적용: 각 수에 대해, 그 수가 다른 두 수의 합으로 표현될 수 있는지 확인한다. 이를 위해 수열의 처음과 끝에 위치한 두 포인터(startIdx, endIdx)를 사용하여, 두 수의 합이 현재 수와 일치하는지 비교한다
2. 조건 검토: 만약 현재 수가 두 포인터가 가리키는 수의 합과 같다면, 해당 수는 두 수의 합으로 표현될 수 있다. 이때, 현재 수가 두 포인터 중 하나와 겹치지 않을 때만 결과값을 증가시킨다.
3. 결과 출력: 모든 수에 대해 이 과정을 반복한 후, 조건을 만족하는 수의 개수를 출력한다.

핵심 요약: 이 문제는 주어진 수열에서 특정 수가 다른 두 수의 합으로 표현될 수 있는지를 찾는 것이다. 이를 해결하기 위해 수열을 정렬한 후, 투 포인터 알고리즘을 사용해 효율적으로 문제를 풀며, 최종적으로 조건을 만족하는 수의 개수를 출력한다.

 

[소스 코드]

 

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

using namespace std;

vector<long> arr;
int N;

void Input() {
	cin >> N;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr.begin(), arr.end());
}

long GameStart() {
	long resultCount = 0;

	for (int k = 0; k < N; k++) {
		long nowNum = arr[k];
		int startIdx = 0;
		int endIdx = N - 1;

		while (startIdx < endIdx) {
			if (nowNum == arr[startIdx] + arr[endIdx]) {

				if (k != startIdx && k != endIdx) {
					resultCount++;
					break;
				}
				else if (k == startIdx) {
					startIdx++;
				}
				else if (k == endIdx) {
					endIdx--;
				}

			}
			else if (nowNum > arr[startIdx] + arr[endIdx]) {
				startIdx++;
			}
			else {
				endIdx--;
			}
		}
	}

	return resultCount;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	cout<<GameStart();
	
}